N=1000;
H=[-8347220,-7643722,-7275472,-7179125,-6842918,-6333566,-5695018,-5013986,-4768049,-4028250,-3641095,-3512595,-3416805,-3122786,-2878062,-2306628,-2210851,-1840717,-982940,-358823,-59521,-131398,-15169026,-14941685,-14479250,-14497529,-13863252,-13800236,-13174678,-13073201,-12455548,-12303613,-12095547,-11560848,-11417612,-11324013,-10787818,-10080979,-9440582,-9382005,-9193986,-8769199,-8808484,-8608386,-24747910,-24252242,-23392647,-22521712,-21823577,-21697457,-21068666,-20720148,-20525270,-20101121,-19419969,-18665733,-18216109,-17411016,-17098854,-16904644,-16017797,-15989953,-15850859,-15649159,-15116023,-15108699,-35692001,-35032658,-34412968,-33669454,-32876284,-32748954,-32152065,-31933192,-31582502,-31257774,-30757014,-30176732,-29520501,-29415703,-28522069,-28083597,-27640111,-27584337,-26822877,-25928017,-25729040,-25646285,-45778799,-45130558,-45097023,-44368342,-43900300,-43047036,-42851292,-42115663,-41539220,-40917191,-40108529,-39664498,-38800829,-38320168,-38380365,-38307333,-37904946,-37410143,-36913269,-36736257,-36059408,-36061727,-53842815,-53257035,-52818304,-52462640,-51686012,-51477962,-51013713,-50301691,-50369429,-50284442,-49413516,-49369831,-48841570,-48609032,-48147683,-47763004,-47001968,-46658902,-46666299,-46525940,-46340222,-46230136,-64346030,-63627324,-62788839,-62478984,-62010814,-61349937,-61223010,-61031062,-60141648,-59319201,-58566989,-57915968,-57715549,-57157468,-56753853,-56535121,-55791318,-55535526,-55339642,-55401412,-54962906,-54075571,-72371386,-72013870,-71285896,-71169758,-70585045,-70337068,-70187863,-69292525,-69035053,-68927574,-68376275,-67753913,-66983901,-67060475,-66812336,-66147020,-66117238,-65878945,-65370330,-64665895,-64393788,-64326657,-81934751,-81629369,-81034861,-81036452,-80218352,-79363680,-79041887,-78265902,-78105455,-77570375,-77562830,-77635354,-77005080,-76727935,-76346129,-75492660,-75227677,-74728784,-73920693,-73317310,-73115108,-72469493,-89718435,-88866749,-88678564,-88678284,-88740604,-88171752,-87471963,-87510646,-87472711,-87059821,-86439702,-86286606,-85670884,-85407903,-85492941,-85211425,-84913638,-84130248,-83591536,-82724147,-82361749,-82249956,-98524612,-98023434,-98091111,-97669041,-96861706,-96197635,-95580236,-95475647,-95360507,-95228434,-94707534,-94214665,-93767257,-93221071,-92761418,-92344160,-92150171,-91392453,-91080399,-90816649,-90904362,-90030707,-107633085,-107579116,-107131624,-106794144,-106288665,-105851350,-105014742,-104998113,-104796014,-104646105,-104447856,-104408082,-104304738,-103470353,-102776312,-102245255,-101624716,-101693384,-101328539,-100479685,-100166328,-99358785,-116516385,-115812866,-115007337,-114294964,-113938033,-113203023,-113282657,-113215988,-113298623,-113045983,-112915947,-112555358,-111961297,-111535884,-110767847,-110096774,-109520801,-109456742,-109093931,-109013879,-108805022,-108118896,-124975869,-124192929,-123602396,-123646771,-123349764,-122831039,-122663475,-122445803,-121804066,-121744077,-121168886,-121001962,-120571070,-119912424,-119202344,-118335561,-118013814,-117769185,-117786877,-117518993,-117195352,-116830972,-133156131,-132841312,-132863475,-132140574,-131280824,-130470889,-130033346,-129909730,-129200370,-129237301,-128511981,-128479889,-128298650,-127758818,-127548759,-127489221,-127370672,-127312260,-126721241,-126363275,-125479589,-125473825,-143106639,-143187578,-142382654,-142131475,-141678925,-140808485,-140106964,-139772164,-139868563,-139199658,-138601193,-138205801,-138194637,-137873962,-137656004,-136893981,-136561946,-135695481,-135264541,-134432878,-134132687,-133448801,-151498799,-151150874,-150312252,-149660376,-149717224,-149231019,-148665100,-148185493,-147549888,-147005970,-146843859,-145962771,-145207173,-144599026,-144429371,-144511087,-144410490,-143863651,-143903071,-143735739,-143710613,-143135471,-160096463,-159285827,-159019004,-158722816,-158089461,-157428217,-156529676,-156552595,-155941225,-155636103,-155208194,-155265625,-154666712,-154029201,-153541224,-153028722,-153064872,-152892337,-152707900,-152567408,-151764080,-151830323,-169069792,-168366747,-167467760,-167417214,-167463486,-166792163,-166388492,-166427213,-165754698,-165767400,-165757712,-165161734,-164296278,-164205587,-163729322,-163220684,-163317033,-162611261,-162378488,-162118067,-161646716,-160973238,-177064152,-176993544,-176846019,-176039160,-175974715,-175858859,-175680683,-175044535,-175117251,-175143030,-175033588,-174334013,-173710372,-173631636,-173147947,-172252845,-171939654,-171223136,-171285138,-170450014,-170209348,-169869036,-184492419,-184425282,-184242671,-184272609,-183794285,-183074581,-182948680,-182284608,-181986985,-181676833,-181593935,-180971080,-180726283,-180358994,-180031860,-179233566,-178926559,-178977607,-178616346,-178128474,-177791649,-177569745,-197208360,-197000249,-196190498,-195645979,-195299201,-194937294,-194278310,-193743607,-193121195,-192532849,-192053657,-191533954,-190818079,-189918864,-189373708,-188912609,-188233032,-187574348,-187314503,-186684210,-186123847,-185344441,-204667508,-204501971,-203635872,-203501841,-203032101,-202973214,-202748107,-202006759,-201213776,-200444620,-200437796,-199965656,-199113309,-198680506,-197920304,-197132475,0,462015,381923,578958,1207316,1573801,1577825,2433730,3271023,3435107,4117314,4713403,4640388,4995812,5709714,6309483,7082940,7441049,7569875,7875065,8214641,8722083,8648444,8697536,9074996,9797079,10123063,10654288,10652874,11056256,11200610,11248364,11622763,12077209,12252240,12722827,13620610,14311443,15076356,15582998,15588079,15912340,15875451,16558447,17178183,17671797,18347618,19204199,19709138,19748931,19724252,19702727,20148172,20636991,21487038,21454024,21403172,21742493,21949394,22535323,23194176,23669000,24546839,25386209,25730806,26009884,26655038,27225075,27539028,27659242,28169966,28324187,28924633,28938360,29799489,30244504,30548600,31031165,31841347,32363357,33083547,33095656,33000057,32983762,33597341,34371225,34672279,34735248,35246158,36027429,36791176,37324265,38003955,38211223,38641387,39255454,39519043,39469481,40048719,40812774,41362730,41868046,41970045,42360621,43109321,43029867,43720814,43742034,43880244,44310041,44943761,45197160,45643442,46124324,46551686,46944694,47368385,47292495,47470885,48273910,48785230,49137229,49355703,50057369,50599296,50630792,50943738,51065664,51190766,51861086,52321825,52802883,53113059,53100510,53767889,54509230,54534049,54850319,55103654,55270912,55967132,56213802,56800428,57153194,57476409,57512217,58337636,58333331,59007126,59503168,60304903,60242713,60313669,61145908,61227774,61141578,61704200,62470206,63277351,63909992,64096791,64708698,65279828,65597803,66056352,66468603,66443916,66887870,66797377,66943108,67231943,67509631,67516046,68175438,68749172,69292098,70123856,70040040,70267254,70874574,71167554,71218640,71994337,72019933,72433941,73157502,73410817,73975008,74580846,75356635,75655188,75939385,76475107,77003714,77715915,78511807,78507137,78624773,79352588,79540668,79806536,79711273,80337010,80833906,81219053,81410280,82188555,82631889,82724694,83500782,83803608,84622850,85516833,85635164,86311888,87134367,87539037,87733512,88234525,88353272,88762382,88740474,88875100,89707918,89973868,89890415,90191840,90381402,91225891,91563225,92453168,92887816,93463638,94230558,94300677,95099253,95735317,95849300,96013836,96566452,97284649,97784970,98283177,98250254,98977680,99488578,100313074,101102589,101303417,101235120,101827504,102089904,102024328,102275581,103167457,103649097,104277524,104319685,104940472,105577314,105840171,106440859,106670298,107543874,108181195,108502979,109215522,109640812,109876202,110439479,110361310,110758289,111100655,111067810,111910479,112262936,112243638,112520295,112988523,113440603,113429390,114315097,114228637,114367403,115254781,115733891,116105155,116894859,117032251,117532451,118068592,118568882,119169268,119118888,119086824,119762378,120370887,120692984,121112359,121851187,122159688,122135211,122887834,123745793,124421697,124837584,124843939,124826680,124960428,125222374,125183192,126072022,126545978,127354851,127680068,128467785,128473551,128500848,128781220,129551412,129529795,129797291,130422379,131122030,131586082,131821667,132504126,132680514,132908332,133270751,133841272,134494960,134634773,135508823,135873062,136465961,136950021,136905144,136891915,136860886,137753432,138393507,138916892,138865425,138839006,139484909,139539140,139504041,140110748,140890529,141693922,142156195,142658186,143334778,143635014,144264883,144725586,144741289,144685175,144586951,144978646,145398164,146173935,146777275,147534825,148256723,148426972,148554917,148868245,149041589,149495585,149818955,150327316,150524409,151350482,152250471,152219095,152724054,152942460,153139114,153146434,153728563,153730970,154451445,154930412,154994990,155296608,156179489,156540451,156877337,157178996,157786360,158591718,159029688,159187759,159847673,160391337,161018692,160989600,160946264,160875669,160994539,161399305,161419451,162296965,162660238,163395168,163697790,163954953,164481600,164750734,165115054,165607205,165603660,165927090,166189200,166802897,167402862,168216286,168785819,169655866,169958872,170609112,171488889,171853567,172706862,172902937,172837706,173555125,174254090,174919505,175786976,175922467,176237945,177135073,177404164,177918535,178777660,179347488,179674864,179738064,179880009,180400536,181236115,182034849,182198215,182798213,183351567,183767379,184322708,184444699,184562045,184479090,185374465,185972543,186222567,187031166,187865683,188364876,188444556,188947883,189314883,189337103,189368351,190261794,191099840,191219916,192007304,192387517,193213095,193601718,194107745,194615438,194751569,194978874,195372473,195972632,196421125,196376501,197267093,197468628,198053633,197956664,198654377,199441069,200276149,200611083,200888930,201506307,202318151,202410534,203069407,203413036,203507984,203480825,203553779,203785326,204388829,204328358,204593125];
X0=550495244;
M=7000;
S=[925,59,386,975,536,473,648,921,913,54,108,649,56,753,822,399,894,418,303,355,426,777,718,614,956,847,228,70,821,147,935,925,603,781,561,907,256,422,441,278,971,756,79,728,901,657,44,224,716,189,502,463,770,534,63,691,974,326,623,614,249,148,540,863,17,656,184,94,688,826,82,364,885,851,42,832,665,410,41,642,658,799,45,890,738,403,584,401,88,36,50,854,357,196,393,569,311,290,591,50,960,663,803,754,783,170,725,935,149,611,878,963,568,386,773,182,866,423,762,918,714,827,349,781,193,549,126,490,677,109,414,430,648,700,652,671,929,256,656,111,793,859,771,661,599,92,956,113,322,68,275,236,773,74,592,29,45,517,155,348,236,120,837,953,560,504,69,93,68,247,11,551,389,180,192,831,189,999,107,365,514,160,820,490,159,432,603,68,505,134,961,597,626,362,284,925,17,853,798,146,350,341,847,110,177,364,157,888,979,714,50,921,411,21,101,607,353,623,702,612,29,975,638,599,96,149,563,896,745,497,487,792,952,508,442,622,885,133,426,42,489,812,545,36,763,706,342,189,675,685,57,36,897,663,371,929,62,143,859,388,657,46,257,926,882,275,757,189,313,238,519,899,927,327,784,520,771,110,287,434,5,644,172,691,301,144,696,194,812,826,338,560,121,283,386,227,388,201,360,877,901,710,628,365,197,505,807,787,859,339,552,984,567,139,327,563,801,344,261,804,474,981,17,979,177,295,851,641,78,912,211,989,97,343,306,927,619,180,470,687,195,679,1,902,361,617,595,450,910,369,138,245,640,415,216,15,601,796,972,774,720,542,422,420,502,119,967,1000,977,975,789,227,731,876,146,291,715,304,718,330,2,242,887,967,686,890,959,482,545,912,613,516,202,693,753,676,154,640,12,986,687,641,796,86,771,617,811,713,117,254,889,2,630,586,20,641,36,365,718,542,425,957,430,490,12,660,452,11,526,449,993,611,653,924,876,154,603,605,837,230,279,693,428,545,354,3,321,506,170,671,181,874,857,10,31,719,550,754,687,11,58,417,166,141,452,342,411,837,803,842,678,980,114,636,463,233,326,364,630,164,313,570,532,157,801,158,352,509,793,817,539,355,918,954,963,719,882,753,10,161,76,798,551,298,988,378,642,848,674,324,580,717,535,4,523,753,426,243,713,66,795,287,54,50,986,954,208,560,1000,212,265,37,764,483,120,247,94,889,389,352,758,101,209,655,293,623,154,156,858,87,962,24,453,966,249,554,582,595,469,266,6,646,576,776,588,376,689,237,232,383,240,680,706,605,646,193,795,962,378,424,282,764,60,854,111,853,732,993,338,92,34,251,212,337,127,884,12,796,962,794,570,430,227,191,670,630,115,106,161,380,305,356,682,713,477,139,201,547,831,697,46,468,327,845,898,91,206,583,364,385,227,288,716,629,790,15,538,319,168,268,687,607,544,303,298,933,926,137,803,674,218,849,850,53,149,287,56,270,613,259,748,109,292,974,190,851,402,190,71,887,749,69,581,145,191,387,954,490,239,582,165,640,693,432,863,877,282,56,470,449,284,111,28,994,997,795,736,906,637,318,51,288,154,919,395,660,990,94,834,814,536,628,375,439,424,592,171,134,279,10,44,947,451,714,4,407,431,513,114,472,168,894,799,400,727,473,609,559,165,714,786,27,385,498,65,838,867,735,103,471,964,859,450,598,843,390,348,83,128,302,860,999,11,261,755,425,156,466,471,889,636,774,922,752,378,151,844,908,270,983,275,751,177,845,817,496,530,737,140,664,817,460,743,510,22,221,975,314,609,236,382,980,667,793,162,932,219,757,998,635,98,943,23,200,742,975,503,275,449,493,349,636,490,610,625,668,697,132,371,10,263,573,660,302,778,709,459,249,908,66,240,193,109,230,787,912,611,808,157,926,960,993,549,353,355,311,771,651,612,396,671,411,740,599,146,729,233,888,635,109,117,952,810,192,456,390,135,545,824,858,259,288,831,276,309,918,100,261,117,889,767,532,179,323,945,921,416,724,105,764,995,802,15,422,188,895,243,653,779,146,765,443,193,131,62,736,997,162,469,58,847,24,58,291,263,644,598,866,694,702,576,320,427,631,288,11,190,661,510,397,239,930,906,773,759,717,261,371,429,895,62,848,97,407,309,499,587,661,123,612,244,313,263,403,459,347,177,905,144,124,905,357,932,795,688,671,973,128,788,463,853,451,351,38,291,853,241,266,784,165,848,837,906,355,70,215,51,768,818,966,314,162,844,420,640,603,429,664,155,155,467,419,397,160,448,595,381,476,972,858,844,398,397,799,776,582,181,122,963,260,403,404,732,625,207,156,932,716,570,402,457,693,275,974,749,493,442,585,711,34,511,962,344,54,674,329,198,753,708,598,291,81,580,930,142,248,298,931,424,589,959,51,383,432,826,82,29,49,427,318,369,225,586,857,324,127,399,586,516,123,451,434,171,310,93,591,697,982,525,675,532,557,124,149,710,458,537,205,381,782,116,772,932,248,981,625,640,192,324,100,451,254,794,965,691,314,590,277,339,981,225,715,464,14,161,111,932,813,96,241,150,346,309,866,726,862,960,344,924,416,122,237,497,944,257,121,60,647,607,890,541,811,836,946,980,94,174,120,642,968,959,517,286,959,502,495,128,605,947,856,456,913,303,215,519,499,64,148,940,731,472,480,551,10,503,682,24,63,763,626,184,138,854,408,790,644,687,197,634,931,206,584,852,569,116,633,845,678,40,424,236,464,890,126,281,593,786,329,308,592,176,995,878,581,141,316,510,672,904,482,468,474,289,807,672,282,105,650,891,616,631,892,444,653,931,971,195,543,549,745,360,904,789,413,508,687,756,367,14,885,201,872,670,145,284,839,788,843,910,412,305,923,478,23,804,417,340,521,45,710,440,105,237,737,523,671,818,514,867,83,142,473,114,6,96,447,752,398,873,259,483,861,927,237,301,843,908,150,405,974,799,740,355,856,697,609,984,104,728,301,202,815,62,854,59,299,202,390,979,470,493,804,32,47,333,80,60,798,988,410,926,876,937,667,542,288,549,554,597,410,566,551,170,882,718,875,477,793,444,692,822,958,881,180,261,377,43,483,35,938,20,687,687,514,451,234,265,719,929,971,642,731,500,794,737,766,702,479,790,590,686,779,65,101,317,125,458,970,434,77,130,430,540,84,336,551,726,208,700,519,925,467,999,53,659,92,192,745,990,716,87,364,161,26,108,461,625,390,760,388,232,200,825,689,197,512,465,741,952,47,664,367,609,428,316,663,169,63,567,13,271,433,96,50,339,120,351,644,701,774,213,637,238,82,112,813,941,205,810,282,66,542,771,174,821,36,321,456,415,450,742,673,343,733,617,607,853,231,442,308,313,255,834,591,796,101,335,408,757,473,707,48,948,964,166,542,617,397,862,530,669,844,181,668,551,10,130,813,599,933,261,308,597,191,655,233,250,880,199,980,797,382,421,758,398,963,425,549,133,798,123,11,899,951,396,528,63,710,539,506,17,988,208,107,25,312,924,34,88,666,718,728,381,587,966,11,224,433,964,661,745,270,216,789,489,769,363,11,759,283,260,840,899,171,508,323,325,937,105,596,462,13,109,523,909,927,143,353,706,64,319,677,414,23,654,927,103,100,786,175,863,248,173,38,485,177,471,426,298,553,822,861,620,511,380,735,717,828,960,118,668,527,538,484,762,7,587,816,109,255,609,515,623,940,78,211,271,112,570,226,670,394,651,663,122,578,299,162,981,432,905,332,390,909,565,148,502,496,16,282,715,217,889,62,503,169,496,737,425,550,205,42,82,738,872,105,264,173,50,38,165,629,666,90,584,332,456,403,322,441,533,123,705,500,808,330,167,829,809,366,676,581,752,665,830,891,445,962,815,463,457,618,389,402,603,207,771,858,91,355,174,521,842,765,592,982,383,493,455,426,146,740,622,164,963,161,26,172,27,796,381,626,504,845,462,814,60,133,269,361,887,179,746,26,975,295,446,985,454,633,672,815,619,26,384,138,510,728,622,580,624,829,115,644,471,57,238,523,925,274,591,320,394,298,750,602,356,216,652,892,789,917,256,707,756,7,714,913,97,576,162,109,717,583,961,935,814,604,798,807,591,872,865,918,285,898,434,75,369,594,818,982,52,248,400,128,269,605,236,799,220,312,198,877,490,233,295,378,606,840,246,404,960,950,419,693,40,193,214,396,582,531,304,225,435,868,944,372,710,42,702,78,255,71,322,966,135,266,229,156,229,20,734,513,177,859,157,235,555,209,10,412,995,565,758,83,178,23,384,729,247,736,64,205,283,519,375,887,684,708,139,23,444,551,294,885,682,201,551,762,214,705,759,845,577,783,332,126,89,899,192,942,256,766,434,347,742,582,99,423,209,949,257,217,35,787,750,458,299,534,1,25,929,432,667,261,462,240,202,697,896,863,792,994,489,347,364,850,585,806,399,184,182,207,911,324,170,806,46,78,732,676,827,591,932,808,967,390,299,10,568,459,1000,610,856,703,427,473,870,936,84,102,939,264,27,241,149,287,849,442,790,291,805,842,645,286,319,447,19,727,256,979,622,454,663,542,224,147,100,46,265,823,455,485,119,137,744,858,140,289,376,454,246,272,934,791,512,620,930,495,663,495,37,733,45,632,822,441,256,224,501,716,611,630,738,853,627,386,366,364,762,740,575,441,215,852,47,989,266,691,222,239,123,344,546,719,379,675,13,901,177,821,838,130,717,596,61,476,111,858,771,966,32,686,862,277,967,465,384,442,500,298,569,630,647,328,207,800,449,622,660,665,697,729,975,223,823,131,248,556,59,219,664,23,118,457,542,600,887,301,194,576,686,560,436,710,3,657,68,26,55,560,411,572,945,398,144,93,65,337,867,20,167,235,141,609,804,76,645,492,271,610,563,30,824,887,391,925,967,810,953,92,77,187,586,952,721,770,681,938,291,952,398,107,899,148,930,194,698,222,868,744,599,503,740,195,602,421,698,77,323,698,183,909,587,741,353,539,537,703,738,232,141,959,922,171,608,805,431,612,376,321,723,923,575,891,133,905,12,380,989,493,632,331,716,927,697,304,576,39,609,604,731,14,655,765,829,378,124,965,868,654,126,363,802,359,63,608,518,70,470,291,200,164,428,435,305,16,199,571,543,779,721,328,964,947,937,684,696,514,80,558,545,159,788,182,153,2,671,692,607,292,112,289,699,588,552,908,286,378,333,701,767,846,425,957,230,825,915,762,803,730,740,702,766,185,858,321,952,630,647,577,984,770,842,440,94,755,460,653,715,700,884,984,438,514,833,321,191,694,662,217,382,249,672,583,955,242,137,35,863,610,615,150,577,351,189,998,169,419,952,717,104,973,402,434,45,733,761,310,920,964,920,344,833,769,740,944,529,692,967,886,382,61,328,402,882,117,151,253,765,411,204,958,85,87,272,957,780,913,426,235,585,978,610,70,788,624,112,528,598,222,757,976,117,297,784,799,547,306,65,756,280,50,616,143,266,280,430,408,59,109,882,47,10,343,628,765,143,760,668,337,19,543,131,787,261,572,688,883,341,272,643,354,451,282,684,303,127,634,292,250,650,448,178,76,211,525,782,683,722,160,192,169,408,585,585,774,716,224,208,912,998,326,21,425,710,729,728,704,484,484,178,85,945,468,698,352,564,626,408,290,749,927,444,146,413,474,15,304,91,100,568,461,831,91,727,295,185,409,204,608,666,853,456,976,64,471,586,397,197,576,698,961,17,775,81,771,682,364,421,907,594,711,248,753,888,785,721,934,316,393,841,553,575,551,526,578,407,979,34,122,54,614,892,527,652,254,445,995,151,614,163,333,641,115,136,598,129,390,419,229,831,832,605,378,300,200,36,693,526,807,770,662,943,723,414,94,495,214,553,132,972,623,657,320,152,358,776,354,314,180,645,27,634,544,57,914,89,554,522,975,630,498,954,275,201,137,976,180,906,334,261,804,433,57,495,123,399,250,264,159,19,818,711,594,389,287,949,627,334,756,841,514,765,494,490,983,458,902,667,219,421,989,889,861,510,530,78,205,334,510,168,748,804,999,10,352,425,775,137,123,771,389,319,925,492,441,491,564,403,116,461,826,632,565,37,78,852,324,196,136,301,721,817,48,237,845,652,295,956,39,277,348,896,383,53,79,347,397,859,489,684,426,831,776,819,668,9,534,65,790,994,378,348,253,209,5,718,194,382,326,7,726,473,581,357,552,323,826,306,105,531,237,245,775,761,135,478,476,413,503,958,199,200,885,844,520,625,89,856,776,160,276,146,734,397,725,362,842,817,516,249,988,59,362,598,77,499,621,569,588,17,207,723,681,382,256,651,716,81,918,841,926,826,635,869,221,233,174,847,764,663,951,552,656,515,358,87,586,845,740,132,179,869,688,872,746,868,322,378,616,953,371,770,643,548,593,208,477,365,718,405,165,341,802,751,283,107,963,240,840,47,307,600,299,258,841,285,700,26,261,809,259,569,23,155,593,646,896,315,709,314,959,554,743,635,428,254,887,299,360,425,814,153,225,507,218,318,801,610,406,784,727,552,983,209,772,684,798,832,759,998,972,262,944,695,192,537,927,246,443,987,588,835,99,259,752,502,986,850,170,575,831,566,562,703,850,121,248,277,900,874,629,1,916,322,24,396,986,983,417,469,910,435,545,92,769,501,254,409,722,118,298,740,721,132,77,446,174,313,805,310,234,901,532,356,323,910,33,345,644,838,484,956,554,483,613,773,958,448,957,228,969,866,747,57,130,3,527,685,194,153,298,895,71,175,450,808,339,850,265,926,829,180,71,803,277,420,194,158,236,634,132,183,713,342,604,431,476,657,842,100,853,738,630,624,733,633,545,739,275,398,682,35,471,250,265,714,185,188,743,439,146,340,402,98,456,754,796,828,294,319,812,827,993,330,587,761,698,371,800,94,346,194,83,360,248,544,204,321,421,564,803,456,799,758,849,253,976,54,293,865,919,925,463,347,36,650,703,187,344,389,166,729,394,198,619,645,874,134,590,152,864,28,520,201,805,768,359,320,568,218,405,614,49,203,202,74,320,42,764,500,110,967,533,428,473,690,940,290,564,516,177,479,260,996,108,866,490,514,998,147,735,150,446,531,898,225,980,449,188,754,937,325,411,601,371,591,865,615,220,320,173,58,988,30,335,524,385,347,40,628,749,823,431,427,55,88,748,967,399,424,919,74,901,334,673,419,10,522,721,451,85,877,207,656,950,589,355,356,334,860,822,318,139,994,310,943,887,557,582,501,369,287,403,650,666,519,822,381,225,213,552,151,286,34,672,286,297,997,879,372,42,70,171,144,426,637,686,891,416,994,351,627,148,598,238,266,502,224,508,431,287,680,72,907,558,95,690,268,827,996,626,564,207,951,249,2,808,712,870,623,760,239,841,922,503,213,842,106,635,777,498,42,374,11,151,247,487,188,476,219,414,931,702,316,523,152,974,157,847,963,253,315,737,229,850,560,425,12,118,978,256,690,919,228,708,959,647,307,127,241,149,945,561,34,753,669,120,729,380,23,374,518,573,391,330,666,980,630,780,451,809,75,492,747,709,366,371,194,311,463,976,726,215,879,43,393,525,381,837,434,906,641,124,65,372,35,714,535,926,28,790,338,237,619,465,500,226,496,522,941,518,211,553,331,64,941,382,312,633,797,761,219,623,643,467,716,932,415,707,276,103,826,961,306,624,203,829,254,704,706,320,848,486,103,945,624,474,451,432,495,260,333,70,852,805,909,969,279,444,467,787,169,33,504,68,57,764,107,906,183,110,260,895,43,469,387,674,109,948,601,539,942,624,869,330,629,322,567,176,787,547,959,892,230,994,294,326,728,832,427,439,376,491,806,725,854,805,392,282,283,13,903,718,653,979,797,623,958,472,841,247,22,363,780,717,147,972,92,481,631,227,179,75,673,25,208,260,721,141,148,507,464,175,141,832,852,663,893,588,239,598,443,397,729,706,88,37,88,918,394,11,846,679,987,200,858,334,66,659,620,740,264,868,285,896,59,875,284,323,93,544,969,843,29,4,868,658,364,110,477,431,248,78,173,602,307,709,659,476,404,57,159,892,772,244,834,530,577,349,75,126,221,581,834,769,471,379,919,322,408,878,674,377,639,33,436,686,851,89,244,18,223,696,874,876,768,157,207,236,256,72,362,418,909,865,363,558,346,833,434,281,468,119,136,978,773,339,915,866,468,726,973,711,321,366,318,659,196,845,340,653,798,395,617,750,294,822,268,908,316,256,389,425,328,776,141,100,955,486,474,989,204,306,550,333,179,541,49,419,240,870,593,175,756,917,64,721,750,403,677,498,654,342,544,393,828,360,154,254,409,688,153,849,748,15,784,258,85,436,580,242,300,7,998,808,682,856,319,245,102,383,606,47,464,333,171,840,96,529,879,327,975,555,697,669,76,156,57,488,303,34,983,354,752,759,803,18,960,770,854,976,14,900,7,637,514,596,38,584,900,889,212,273,941,702,96,776,916,784,690,150,481,401,482,250,924,456,200,308,822,901,421,772,622,616,632,658,756,122,42,207,280,978,977,210,627,232,39,492,268,989,467,411,379,535,461,697,489,128,262,469,892,232,516,888,534,341,729,752,942,609,469,599,941,363,190,348,449,899,486,231,972,641,748,169,213,46,336,305,669,897,731,511,858,82,803,539,398,274,794,134,456,751,344,191,529,179,275,46,287,917,149,67,292,822,357,214,807,685,987,728,345,786,408,208,312,493,683,287,342,454,396,131,2,286,747,294,597,180,72,167,429,8,828,751,548,771,678,860,57,923,734,112,741,474,429,106,790,775,58,58,406,491,453,313,653,293,38,894,201,244,477,513,356,155,19,458,356,983,591,2,556,786,289,384,529,907,506,788,333,50,137,862,126,23,750,934,207,67,17,781,997,893,971,914,290,925,506,70,813,396,416,679,238,120,37,311,397,187,359,5,603,381,512,762,287,668,983,692,321,250,44,157,745,846,584,148,496,344,417,409,813,200,321,365,8,223,448,983,625,412,988,967,329,271,967,357,975,73,912,114,667,216,735,933,805,974,741,758,486,586,737,781,101,141,747,938,514,422,771,918,245,381,209,72,311,402,358,81,263,309,937,279,197,871,858,956,153,191,610,415,12,525,880,601,133,298,924,952,420,92,998,302,585,349,158,490,125,532,13,12,15,602,514,637,23,126,925,988,557,863,647,305,322,488,727,900,677,942,77,886,470,795,993,214,509,862,931,236,803,511,964,600,559,238,275,227,313,772,201,723,826,480,556,850,600,482,214,240,573,395,182,883,512,809,276,605,898,78,233,141,897,882,339,980,175,827,892,288,603,699,908,251,334,561,913,100,190,341,13,739,413,111,135,241,506,176,319,789,742,7,734,871,959,572,962,719,687,448,725,270,701,585,607,995,386,921,214,886,892,287,500,199,669,932,936,943,716,807,274,972,306,96,883,696,141,335,2,91,663,780,79,99,967,456,218,42,534,546,643,119,570,186,923,331,437,241,289,844,174,973,517,652,454,176,856,474,484,449,689,102,431,737,232,689,298,15,773,562,26,826,560,153,113,701,466,126,181,453,786,674,585,468,376,172,130,673,781,956,18,668,920,858,567,101,857,255,668,453,728,873,566,195,310,906,583,447,281,410,622,114,595,671,179,874,292,43,230,937,634,613,680,367,943,398,336,42,410,452,462,476,139,865,362,868,299,796,557,122,872,693,622,934,828,957,725,313,199,539,210,18,407,751,270,969,422,593,728,231,963,114,768,810,94,233,542,732,440,534,603,388,56,457,846,891,870,35,295,392,594,706,622,723,772,688,652,564,261,581,528,947,988,903,506,521,193,200,258,429,173,975,857,383,807,941,390,112,503,456,305,70,701,570,850,987,193,234,562,246,268,928,448,448,237,725,244,656,236,576,742,133,818,185,599,810,990,632,526,204,856,702,75,93,864,898,990,604,183,108,736,233,531,140,728,772,518,627,118,118,240,775,931,470,199,610,749,556,269,748,934,17,153,819,29,323,923,833,35,980,924,125,598,108,394,952,712,185,167,616,784,885,771,735,295,95,836,644,435,303,324,335,710,405,434,833,591,458,990,33,439,5,913,983,716,854,481,123,928,430,392,350,498,107,118,679,427,943,473,590,865,898,163,571,902,762,523,887,153,737,769,680,315,798,766,688,666,969,833,463,840,594,730,619,932,858,737,302,271,768,854,903,503,708,938,311,606,895,204,428,523,239,316,992,159,174,211,162,777,139,680,458,544,911,843,681,887,305,84,302,515,113,435,505,726,591,793,770,862,27,29,530,846,478,112,976,291,215,88,380,711,54,263,94,129,275,28,311,457,935,343,229,39,153,369,370,452,625,96,678,567,944,510,359,352,28,267,423,247,103,85,493,677,401,598,242,897,136,909,532,643,622,362,237,531,202,830,580,154,996,479,161,751,868,31,397,322,979,774,199,347,440,986,183,227,339,181,61,33,917,750,602,861,524,525,877,463,18,347,430,968,647,303,933,911,857,881,771,732,986,529,142,415,825,535,808,705,342,44,713,961,73,295,663,183,115,824,660,67,123,800,655,742,473,214,505,391,942,802,328,462,952,380,734,395,953,100,346,703,176,203,492,161,742,872,469,161,26,659,44,439,356,493,569,580,876,285,164,319,610,563,78,816,391,79,390,511,602,426,428,941,859,922,672,857,738,249,659,947,80,583,723,724,868,826,202,458,726,12,368,55,111,284,835,682,861,634,477,604,178,871,949,667,118,97,276,641,935,226,368,13,447,994,259,976,349,735,804,872,321,795,579,439,75,565,481,204,740,197,389,88,515,948,215,993,120,536,711,369,660,972,358,935,765,741,11,36,293,716,190,70,300,378,279,663,272,686,335,974,451,624,844,332,356,945,704,231,755,240,947,217,840,749,459,953,604,528,458,400,630,457,495,244,134,833,843,111,269,991,820,257,505,339,732,912,140,470,634,542,293,911,934,321,173,422,929,148,387,371,730,124,791,414,345,427,401,136,174,431,89,912,986,163,736,439,964,972,477,115,76,868,16,470,962,938,785,599,351,110,857,126,145,600,47,820,434,17,939,559,170,40,486,105,567,45,470,530,235,8,693,448,989,794,979,925,446,314,774,544,804,760,920,353,489,884,952,609,100,583,678,518,853,296,290,434,765,119,453,189,475,436,310,645,311,880,189,204,561,386,651,369,66,994,662,780,569,704,176,894,598,357,369,470,481,160,295,836,739,249,988,480,146,488,511,666,208,894,768,515,773,154,975,570,367,420,917,55,968,60,1,819,623,715,235,21,677,576,436,381,408,523,834,635,66,164,375,639,290,772,434,698,816,666,20,475,237,558,476,386,160,696,98,848,9,577,790,692,840,208,656,254,286,349,609,302,106,361,320,213,20,298,157,537,84,594,560,748,27,256,330,862,759,165,914,133,178,223,376,99,636,688,965,303,987,271,399,553,481,13,632,786,325,752,456,720,120,218,541,117,568,658,705,865,663,209,227,746,220,173,683,194,143,776,153,200,929,1,366,860,721,617,497,7,815,174,74,608,987,882,474,191,870,260,287,716,847,925,387,103,62,427,358,129,603,744,726,649,727,683,397,823,576,189,10,148,104,604,125,663,407,474,822,488,243,998,462,103,822,273,540,100,823,17,808,376,39,128,35,146,948,358,347,802,400,609,962,145,474,875,655,454,802,330,827,257,641,545,125,578,534,805,917,337,89,264,443,703,554,728,871,51,946,504,618,334,752,813,691,166,612,737,570,325,150,179,31,762,815,651,259,829,565,73,413,119,866,390,21,806,310,849,516,572,831,978,528,697,487,641,83,779,261,527,229,268,698,67,396,227,756,325,506,128,717,437,222,380,20,916,848,693,129,233,680,189,253,68,39,196,975,957,556,352,847,573,39,667,573,843,585,724,962,471,952,659,429,817,382,465,710,226,339,613,909,609,397,919,979,110,126,463,454,553,973,845,200,347,234,706,121,203,925,925,327,809,767,54,252,717,175,94,175,352,589,516,649,129,858,232,808,296,828,114,182,493,557,770,930,289,940,153,924,651,82,822,29,91,270,361,596,241,680,75,881,270,976,867,92,993,262,953,630,130,827,277,814,546,702,816,460,351,751,344,144,323,78,719,243,501,132,101,907,270,216,536,970,972,794,770,992,409,307,330,395,524,609,504,125,86,78,549,205,533,178,991,188,651,771,72,40,687,579,80,59,394,73,589,660,458,141,841,259,337,319,931,609,606,848,771,293,578,143,146,263,243,412,903,335,251,736,666,286,433,193,235,51,902,49,90,70,480,432,896,903,913,908,196,751,8,495,190,804,462,832,463,856,257,927,110,299,547,20,59,955,83,552,118,506,842,306,599,647,183,202,495,147,705,809,117,868,787,301,705,108,210,832,708,10,688,497,549,110,147,529,860,1,734,879,105,370,422,843,981,337,925,637,270,486,346,317,366,810,517,124,213,844,206,777,857,412,182,780,428,130,932,190,989,439,224,285,660,633,578,211,938,666,11,119,61,922,690,90,983,991,39,891,72,155,922,793,846,517,508,479,683,294,852,842,782,308,818,708,63,609,502,4,871,932,401,450,596,349,298,862,56,837,905,625,547,795,798,330,891,191,74,185,434,601,604,391,799,922,508,682,962,553,770,212,772,78,167,981,540,673,938,83,178,51,859,704,78,114,626,139,232,656,808,372,921,445,196,403,96,791,566,49,181,664,838,413,25,999,317,39,371,733,698,600,707,288,765,6,161,866,70,691,925,514,478,462,200,200,204,16,321,205,528,216,793,288,410,774,478,505,771,26,34,800,306,212,524,710,559,621,596,634,451,948,347,252,404,105,31,4,580,621,506,907,426,494,28,703,327,278,835,370,241,508,289,324,426,865,93,307,601,932,415,945,111,244,360,125,682,764,838,424,324,489,203,160,524,933,247,775,819,199,840,292,687,655,808,159,194,877,310,273,827,818,426,497,163,485,429,95,792,614,198,51,844,838,453,190,950,259,58,903,63,47,277,46,141,82,543,443,266,250,711,671,333,361,629,256,63,934,890,344,342,169,621,823,548,770,846,899,185,562,13,278,563,184,354,367,4,316,590,103,762,335,632,732,600,159,344,712,227,902,511,970,869,963,508,738,148,679,167,585,211,457,304,414,263,873,688,513,842,791,717,410,339,827,921,970,602,206,412,288,783,911,148,772,419,238,659,190,677,340,240,951,613,935,259,157,171,977,117,626,656,121,860,126,427,40,346,423,4,245,423,815,579,991,417,5,705,321,266,786,205,312,361,668,119,22,926,85,751,258,194,132,814,492,515,985,67,636,844,429,358,595,874,399,15,544,606,463,855,723,841,389,989,277,474,18,721,988,361,901,139,338,47,422,420,15,579,973,19,545,157,683,416,202,133,294,435,177,651,712,653,278,976,321,517,465,995,863,691,771,228,164,535,739,524,631,858,297,90,425,819,734,126,96,906,824,288,294,543,465,952,18,379,216,551,556,37,134,516,869,941,978,200,924,668,260,633,385,80,436,809,500,131,378,695,518,612,855,891,198,236,18,518,220,73,899,406,936,349,755,29,651,815,200,739,931,704,876,430,706,278,614,480,144,995,455,64,931,374,198,918,101,456,706,235,181,543,222,661,980,29,311,574,736,825,207,894,467,276,621,907,276,244,129,351,915,795,155,905,385,512,940,521,789,396,819,152,399,85,488,749,271,405,4,592,174,835,605,665,171,128,973,64,582,234,76,878,383,523,680,154,863,698,755,452,700,392,428,381,312,219,563,916,243,45,296,345,59,982,380,348,58,812,966,861,703,57,718,949,707,59,973,499,756,781,689,911,196,116,508,146,378,282,725,155,686,389,205,290,1,968,691,943,738,72,719,795,289,431,673,900,446,340,825,788,594,807,744,187,116,888,437,63,964,368,368,618,418,814,786,707,687,578,833,346,441,868,271,472,203,341,371,787,786,172,518,765,799,121,663,38,587,916,61,900,797,614,67,905,262,414,774,116,92,764,584,805,601,896,944,677,340,931,454,451,421,596,898,559,437,619,197,985,939,160,334,73,895,628,837,832,249,974,755,789,274,510,294,736,473,836,464,906,910,601,673,866,489,60,919,968,299,29,28,252,466,628,359,230,905,962,776,87,613,502,631,406,199,488,221,771,968,320,649,335,327,575,803,689,245,892,356,785,968,351,546,871,930,296,999,580,130,416,410,166,32,958,644,447,805,650,500,855,976,341,194,108,57,525,982,528,408,948,152,930,990,33,489,434,426,685,904,385,652,70,477,141,516,974,625,944,763,436,386,266,495,265,530,89,179,587,528,879,156,940,621,379,907,379,96,957,601,985,320,478,533,748,536,940,336,726,853,585,872,358,289,445,943,629,763,710,628,561,235,542,879,860,209,220,769,197,214,536,105,189,297,539,167,386,938,476,907,414,562,931,254,88,447,632,239,329,987,339,734,711,878,749,779,916,174,909,191,199,869,107,352,273,122,280,569,249,53,227,655,94,102,876,435,147,406,483,262,805,44,512,295,70,864,644,71,196,59,774,852,994,699,590,192,213,498,173,154,751,391,10,186,662,731,109,785,909,613,574,862,953,485,166,385,404,27,243,26,413,583,391,930,940,746,938,496,409,819,906,772,701,90,633,678,271,968,182,111,7,651,473,469,637,381,547,899,698,621,482,14,949,524,136,623,126,849,325,775,653,316,727,45,363,813,744,146,807,860,919,980,9,850,140,669,273,598,240,300,152,320,938,929,933,688,434,901,536,759,768,759,801,556,340,575,633,775,87,797,415,969,64,914,435,848,799,917,69,606,941,942,782,811,665,661,861,661,171,35,666,910,971,710,829,461,201,833,503,114,214,129,247,749,729,95,373,631,138,668,633,223,218,815,292,421,352,41,205,522,988,112,684,956,894,30,385,445,463,706,53,85,413,404,407,778,194,877,743,942,910,156,774,600,471,345,338,528,607,404,389,222,357,886,510,675,297,958,854,566,972,964,203,959,740,184,167,7,35,899,441,588,857,579,258,328,580,579,832,266,966,448,549,51,198,995,768,50,796,709,370,799,721,117,25,386,363,996,847,627,4,840,947,907,780,851,638,545,673,860,966,333,309,867,173,639,367,769,498,584,103,501,134,647,782,551,823,980,547,95,903,320,574,6,589,57,695,611,426,297,446,566,748,448,500,839,973,716,576,775,836,231,978,556,106,344,667,393,646,791,322,403,287,532,911,83,920,944,290,210,790,90,603,159,971,282,843,411,381,193,769,940,215,69,382,316,798,112,856,10,204,514,225,430,600,193,128,609,466,95,253,98,690,387,121,897,593,485,794,894,110,669,186,426,401,516,129,756,210,937,293,508,922,748,160,562,144,430,393,191,340,565,312,705,934,115,646,3,471,231,481,738,582,458,747,719,979,627,588,659,198,154,258,525,464,807,623,678,128,682,458,620,582,180,243,401,458,396,851,724,661,858,961,85,310,102,157,941,261,121,903,171,954,610,343,647,462,809,318,873,736,695,259,2,400,418,646,17,566,412,696,150,923,733,176,593,270,763,782,75,239,424,938,410,870,371,4,553,428,188,29,485,272,867,692,823,578,985,153,880,498,205,445,855,721,743,847,765,454,200,887,392,273,22,29,306,178,187,970,34,514,679,772,424,368,880,485,389,532,496,933,80,295,630,842,561,151,90,782,720,150,452,584,326,451,405,736,42,207,508,431,924,312,249,547,340,64,781,942,499];
X=[1000000000,1000000000,8102781,204951391,387133571,48383707,205942528,560351658,382300083,13277410,1000000000,102932675,24850507,211820980,164915936,29106100,114601782,312089051,503906813,391983908,1000000000,1000000000,139542697,492996938,144982377,328462342,109579873,23736671,114130260,140605415,518092242,83846005,481958634,20142677,204896276,275887279,87887035,1000000000,23085148,492670185,3530007,44845560,40227715,751385669,503377284,12247326,110724453,151882036,43401213,137148193,294052765,1000000000,278558698,1000000000,53182239,952081013,463636841,51052537,213179277,91274307,32692503,96602691,74867588,95439987,374402849,2595324,669269647,11722465,60368987,1000000000,624818707,26281007,129017947,33179823,230571165,11630228,133897725,164538933,347736265,1000000000,194228224,5919329,318696025,42876006,387013619,1000000000,270665235,44163078,245867233,14251840,1000000000,482139407,15483400,509435658,153637018,75902733,273471195,55937177,200523581,192442771,1000000000,191845608,74287011,324640291,597652545,176436247,318224025,325310751,127820149,1622598,55046386,221710800,586673772,585110267,129376086,395839106,11697418,1000000000,155584487,41012173,78017280,66676172,218177265,1000000000,422931971,18319555,1000000000,35734033,328444780,51700920,212360975,247144485,11331755,78180467,83890518,1000000000,127171233,138304388,196559440,105694525,77201750,104276093,40214599,68143430,248492317,334254520,360270480,153134005,3606067,1000000000,237451104,58950589,523126032,45264179,316156102,28491370,89934259,108204568,712967891,360173784,184433231,8520094,218962880,44448628,147084903,163371362,42791173,195853645,122941384,30728786,58182245,92813798,3866048,240702424,221899096,1000000000,7688995,753430420,404248799,42434770,124454022,45012668,141057139,181511431,189253725,54257121,1000000000,505376541,65592272,413398280,264370141,371065548,442854141,374353717,1000000000,109100762,120202909,141705331,1259466,101400098,120118849,1000000000,16645631,1000000000,768508754,933276603,26848843,621833417,118065028,2871837,95819155,579759361,661068080,200212754,694549186,293100046,647721659,192641266,215193091,113760141,644343529,123273780,524281233,63795677,88159482,238593645,157882989,196855876,832857000,825430645,186458772,1000000000,419238479,1000000000,3926802,237391930,690712341,149857600,385143805,265579601,92815871,146474114,1000000000,48566458,138348617,276665830,187109071,410290380,199516232,356392547,428714338,174515891,327007388,138876075,13333703,8199100,297305789,92379306,181383451,110222393,312362431,23874665,240737114,111595026,218893103,190549807,136317715,611648,1907997,78815565,118582573,323346291,455874618,359839996,57706371,1000000000,615641254,69207901,308392745,145852070,388061422,642877035,74029954,398350716,143338212,267919464,1000000000,574696265,193648895,207460926,8593414,40117566,329157013,72755945,52526658,18834538,583447641,150973701,471342632,1000000000,387177058,259774458,99643282,57593608,16322512,67443051,528736985,565277872,1000000000,134365919,98678604,36414654,8370581,58297021,42319873,72057238,24654342,512135819,98762394,576021115,845972326,485426258,126308495,1000000000,501320061,39166021,7199452,104699926,1000000000,140794414,464063589,44293098,55775641,142539081,109516361,53067996,106378038,686465834,72626289,1000000000,348842002,366188736,759590345,137663638,94836566,4937222,832238518,406303342,158969254,61945902,220751006,41096489,186491405,364228823,149976166,155681140,867505963,389576556,1000000000,630341412,6172719,876211405,31189329,1228721,431713433,395143828,56852125,316050478,420039721,5342266,1000000000,201462962,2434058,1000000000,76934910,143088960,2262441,1000000000,84808101,1000000000,289090507,88633472,59895758,1000000000,39396467,1000000000,1778904,1000000000,79287016,299703029,85957001,179713334,191305232,58208860,99060455,212712614,1000000000,54054693,423578891,18907962,727162087,468185,100223437,1000000000,115845,331261765,156038205,99714607,1000000000,208959523,242207566,131371313,233656153,3201639,96364632,0,180462169,63060885,1000000000,25804321,233592524,647531854,142881953,310214967,158808869,80038344,1000000000,393695338,209489355,151711301,42053282,99082308,927040632,268048581,2703859,23457541,1000000000,340437629,363245617,433220658,456023291,14524863,467069626,887558521,1000000000,309374499,175027071,1000000000,280476915,647603221,279115757,74091623,148724040,81042141,551295300,51984163,50212997,48106670,197194521,11377947,122866163,177533616,32882536,337852528,529142437,120730826,299766167,122227352,5310054,95477477,239567133,63083393,256195935,1000000000,1000000000,614791146,931057852,855407655,6496742,4759786,75059771,12575752,688391275,311912498,1000000000,2952830,146560838,380357282,94175295,203982555,32713812,78890677,95294029,27850477,47178048,163352855,390768960,1000000000,378940153,151016127,8273310,399087113,843262714,1000000000,401372255,142554149,15263364,350456421,322600856,250936416,769907471,66160650,3588350,658497552,443267666,337990739,62823595,114876346,191056131,125557113,41918215,57166239,1000000000,36263969,176877572,412058116,33065583,97843842,302564992,170045657,409756025,11935814,11864282,810776560,19636811,70791653,244875963,1000000000,7460574,156747968,78746549,178982607,1000000000,307579057,908215483,1000000000,272896679,312668352,617816,227399878,20306938,97618171,454741276,84654065,46547593,1000000000,199517653,21419401,494768987,90302624,249516173,620666452,100021231,97468098,219828503,40810098,10792646,915816666,48443640,1000000000,281258876,4395455,1000000000,41666645,274702785,685567188,67989975,311245817,1000000000,1000000000,79982908,1000000000,63103509,1000000000,1000000000,808205386,755062006,85446603,1872508,38011374,200684016,396080025,167779744,10957310,51204184,68950852,112479428,590632240,1000000000,190148199,34575779,6596602,474086731,43761999,234042492,29554895,7886724,828713193,224329481,421896142,709232498,89598402,101846005,339631609,426386627,729700535,126009909,1000000000,106103919,146871743,18177871,48992010,80044820,8119663,153109562,46155066,225835084,212350242,172393625,52638393,97656060,126998241,47314570,46847345,604200391,206118984,49939406,294172289,1000000000,189109387,1000000000,203416800,78561207,30639917,104570331,10594676,14303414,753358513,120474585,43914744,47306508,3516825,170656967,93054992,743729829,1000000000,137322404,255391023,421578297,451943466,101758450,330584864,770022850,53965401,610820158,60183826,186623056,409197025,75223152,130111207,17091120,69677586,101572646,573501474,422856806,94847926,284172332,79019195,1000000000,936664689,640655712,199192413,7643274,651550636,357295669,185446426,1000000000,11786432,27169527,51810145,21115876,379123513,652185809,1000000000,138408483,469031941,519020099,115416950,111199835,552014293,437335011,6663381,181806587,388221619,55832799,6368260,321236813,135732330,190390795,17757267,14667793,1000000000,91911214,21754772,185688107,7847547,6553715,149960001,61064103,27097813,1000000000,47007271,441644980,663571985,80424810,90271959,296833479,126583904,178267991,159612715,7270560,320316624,107566968,434309794,129165629,1000000000,2511532,43991668,260818850,1000000000,1000000000,116279061,150145774,203968064,194450991,1000000000,475583310,78855740,3351308,20266579,16305901,39279731,321079727,147960386,874731210,345782230,76601677,73684740,278971285,93375375,103240413,29001756,248097827,823429729,35050756,645276045,883804385,232247017,155697899,73264756,51339200,6836461,8893502,1000000000,55641343,1000000000,1000000000,786443202,59060743,1000000000,123181990,330963308,99147749,164360229,20330194,196133824,221718592,630442949,515777436,124116939,10213265,510425160,108775804,595993038,101868007,422932600,85699290,41919831,377410387,227365296,24400064,101913102,82630696,232882076,210598264,95977641,181060774,177264222,236288343,133942402,441500760,1000000000,160373540,125195463,56848997,25939192,1000000000,340274168,229915310,204974985,139634630,43583961,221283952,249282300,1000000000,215574014,1000000000,1000000000,637985310,764192602,1000000000,38852689,1000000000,393302968,149370114,93868274,234881570,175692908,190425710,268283566,36489734,617886567,2295285,244536307,14616215,1000000000,123729823,77933321,144160205,546966165,857548449,100307902,153145167,18556506,189960395,393803302,5873549,109387405,760925861,586464590,13882200,563256899,208321307,154475727,4385819,814442996,616042899,184333591,21858702,509926193,759152530,56834176,259397826,35553250,97956383,1000000000,668768443,813373694,43207626,400205937,425941855,11522782,788258793,413780394,575812036,292111913,946800844,160232672,1000000000,297373743,32130344,1000000000,451181051,96067636,1000000000,3657503,96884705,204823834,280619683,57628343,334406053,29829889,287008097,1000000000,492382995,842206052,57607746,10128796,188191886,219705033,184019261,388159521,4343388,103875763,1000000000,98460027,4361592,1000000000,1000000000,38549273,146784163,186933202,57907833,19250661,118154873,174577912,2858802,986159454,1000000000,123999133,262666049,78733682,60532428,91857975,148874459,51951497,42650175,25369092,118919219,498262768,455276707,10254547,495598427,48395383,448038943,998737491,8875720,799128028,283963688,104617167,34233829,1000000000,1000000000,243190706,95013976,393317426,423217596,97624470,692784511,350596854,1000000000,267963766,110727343,104178983,661670486,1000000000,64673444,270173524,221127850,1000000000,178828557,5715897,93662860,101019591,174793942,138872688,157343738,20198199,248355897,298241023,240425586,79783479,218266650,18598039,86641349,61244652,919846,286233918,573752985,137077551,1910943,8910607,57910697,181081294,54790248,1000000000,11964999,127368622,5249015,283424329,20144616,124272036,98299631,372409020,863157581,55484483,43147872,6488798,41659716,101966011,262040260,611931770,56855786,103909324,114040086,360726052,8068993,131622949,84326056,14460518,57586961,35540316,140732688,1000000000,467297711,1000000000,61496252,32523103,42308394,389051519,89937741,547475316,564261,719329619,37730415,50624437,244206597,75624202,232752506,36742545,872322216,192795209,22711643,125392028,163779973,716252049,1000000000,293177801,154400256,173649880,17218528,47037964,290994606,361422668,213738851,240841439,17028587,242015698,345817112,19164326,43106061,191924206,243768410,1678117,22871892,107538990,42323824,415382292,828248600,44851360,38879868,469296889,762563011,147536313,36123695,107222035,451584740,94105213,24217758,189389206,13426624,1000000000,934268052,413243927,58626223,158139326,179085836,5347786,163044182,190667808,362458051,1000000000,179073570,820163187,1000000000,233418294,294700123,971026936,99796147,322315813,197855334,44234091,69942509,30544131,14310533,387030080,46526235,207447411,109262000,762446927,31224583,55378289,9262880,43015113,73192122,15837233,150983021,155720513,2808481,59768381,1000000000,209846060,455554009,16647570,684598525,200004080,1000000000,138254575,638916989,63037666,81487699,510071132,66951107,69592595,19847998,2093076,653534001,89238974,1000000000,185260292,174633321,178160955,316252978,50113925,489563361,433404491,20460952,30310248,138970818,6085954,163694383,479435263,105698096,174433858,1000000000,31719975,87960784,12344843,72046921,170271590,464341647,30095068,643384358,36072907,160758171,241163314,1000000000,198881803,18616652,131586331,107135215,123763126,9095003,820038791,101515117,135750497,348212571,446021757,65020299,283799533,88328091,237933283,163818887,104680628,79083000,148067718,260089034,38767129,442991352,688891600,816920613,120260751,166873998,333553661,606854117,14815938,42053591,1000000000,34890207,230872977,1000000000,113175956,153410764,42574149,778199241,95719951,1000000000,8184971,206527313,70479110,1000000000,83471251,408657805,650123737,1000000000,186273011,244904849,916305216,162960430,289321787,82275655,180225642,523951278,283604823,320111642,49638277,172558339,496495034,253713359,341331364,530598673,74082811,215593260,19423542,176451385,215682935,125207617,1000000000,1000000000,70765548,71171342,947205801,1000000000,260876187,147696666,57226743,1000000000,187922113,159586074,146410489,38401994,28819344,47124563,579414783,70968652,113697092,58147155,95747735,1000000000,155305661,1000000000,433948956,1000000000,167190002,14515011,503485118,475208171,124892700,141766491,320766964,52823996,1000000000,94484600,222294098,76984326,135171692,40766865,170643235,174158613,5200793,278991892,348358456,12476542,207736406,16223407,757569652,61999649,39334674,1000000000,49352501,811073286,251501781,127656870,1000000000,673047151,233952127,434347378,1000000000,20436206,8945507,2178998,269955022,42681143,247568132,309893061,43758328,223138516,519875330,141014717,247809419,123930068,35770521,1000000000,366396991,175040752,183871170,32453156,166146869,537360951,134619653,5955316,53918110,190618235,71461241,13290815,208688879,408631280,511823709,529661237,1000000000,655273965,171010062,5080304,477171305,1000000000,10811614,57196178,49176360,422857404,194668187,584370754,82641169,23735190,361031206,78707783,15890847,199311917,355291485,380479631,258944359,100544009,496911845,307526619,186313784,43853984,63867581,26213680,1000000000,347002973,13715480,396257874,483894166,38456452,18487602,617168717,30966955,248499676,249526832,1000000000,50301563,199309256,63835022,561950646,36552117,113942548,96379523,686133605,688604962,1000000000,744875215,360232657,1000000000,1000000000,141533850,256760102,99363628,44070,54151931,423144077,450609442,312647479,57110408,256399275,9946813,28771192,116737893,121737790,285713330,298065412,29896086,73506285,1000000000,1000000000,252500141,71773088,151712455,4845266,19101281,55743235,207937919,197379166,684112102,108366809,304718058,141202891,31683668,152720721,115242300,454671068,351411246,45199749,44538794,549736770,260181213,393809253,47920100,10540108,158674875,484126362,234958371,14027755,1517574,38667030,183745051,299819907,1120155,8026387,73546490,38098945,128787764,113280877,454504503,300113034,106107736,609774529,20831364,82549176,113484951,262683106,395418515,19915584,211092543,1000000000,42066782,331561074,16306617,131086458,118929645,312089421,124075043,1000000000,334408537,303904904,502703796,266399875,91774234,130284143,213592501,222414036,755812260,12414977,117966222,288461855,124533489,257284099,1000000000,121293801,35662865,19760105,1000000000,255149105,209294268,3323616,164704731,1000000000,26854303,988046246,59915726,73952875,103241721,244134376,360194422,1000000000,105858042,7770545,265701389,250090760,1000000000,559281614,203543820,14707397,337550300,1000000000,1000000000,587836269,242593464,128579696,193759391,28870643,327924123,65371160,157687775,328499157,16014230,23305126,105907030,223496839,608294159,111924425,192540053,141801094,202785060,149649861,961414914,315924294,483359154,236533298,236638401,92899809,17677117,856633146,56354474,99805,94720514,546376570,9913054,79413333,152612474,1000000000,189435576,1000000000,90684757,60507617,16685351,872118205,25924293,426359943,117459640,65923828,123351017,374629296,181948634,173377778,141211885,67318551,70714170,984841384,88708729,481481,317324272,9816369,59139604,48871478,101207638,92937575,506303689,12661781,224062353,1000000000,69141247,174513399,72428287,112793402,306518368,3922664,138644,526535,257802869,696020373,17415599,62584562,250516745,43916221,51891057,1000000000,95717834,115292578,184649005,47645646,185287553,323869103,1000000000,44080290,334566702,146496272,118203345,71995843,6790064,559310780,339473555,469114872,870382697,103304902,302498073,5414737,166118779,393362505,3094429,249300514,93910540,158108210,66891673,869787047,240360522,413960,249376550,87803828,252994135,55993719,155600527,1000000000,451675673,502157700,673623552,228699162,212525961,41280372,245086559,199443277,30620627,91433934,750007219,60266120,1000000000,131904084,189763928,9482284,3644540,36558581,118390843,1000000000,145944405,43017225,986206942,58251186,258600175,88691853,71152082,199610845,37904987,110832072,171244523,1000000000,18566038,1000000000,73217907,60256143,56589439,344177262,1356350,78596219,903813345,21213219,355879584,87421073,11346006,682083827,1000000000,266752918,121352145,1000000000,419118005,100652879,197123695,406028215,273119375,74316024,11535057,470696723,1000000000,25631593,47237623,1000000000,24762052,122948152,126095063,657932313,1000000000,97514851,615346508,30049186,1000000000,16858864,15745401,1000000000,56396943,248935697,822043083,103840008,8007718,323833577,189834217,91722721,1000000000,74047843,75100332,64064040,32180075,1000000000,543889496,29035204,1000000000,1000000000,113121779,205107092,99584474,71224130,1000000000,124313718,2756284,34612230,20639003,395255845,76928268,26361663,208020654,553015747,31614865,36064402,1000000000,75812649,157066855,240890342,1000000000,195260326,159557132,343330082,40598770,23017595,1000000000,464468302,1000000000,978537973,262491157,58432681,353185358,1000000000,113169161,184520441,64779794,287699091,564825944,560040750,52102256,51192286,399891371,76454233,26652623,124185130,118365712,379705413,65266002,382752827,1000000000,88703711,146118563,166239056,1000000000,11988728,4836040,24605028,1000000000,199205338,786618926,212743010,539684635,122138093,838719851,11101891,116256367,182359273,107215037,594282624,1000000000,86263616,267637143,883198790,272792313,320158208,206139177,8532397,5274556,32213628,77220961,13921799,9294734,881797466,24947199,215969051,448556338,1000000000,354548361,418184453,78920751,8658815,104588125,8676255,142919678,284958409,4738446,193872685,539434683,175259801,92100210,29535205,197664806,48419778,569083028,653263601,45401381,53198216,181156099,1000000000,53786375,411195017,237616395,130014857,170422242,449539377,1000000000,85937514,1000000000,1000000000,1000000000,76456068,689578921,19034040,322671839,513101387,46974642,10325053,191048324,318865256,75620110,1000000000,1000000000,462279161,4085473,41149745,73855312,685138981,532450537,217639373,347834801,132979496,63605216,646571035,99720487,294833748,226425822,153361261,282579454,51314286,178650444,600776077,269709068,128550663,16341770,721989295,5674158,178475009,69103056,1000000000,76994730,265720583,169560629,1000000000,81351426,325252654,173630828,14088605,114369759,156141804,97250941,124571855,45450844,24429591,770618513,321271364,118491348,73538320,80249443,104326410,157616341,34594144,8728554,520868324,13492245,49627432,3179022,143108082,3424141,22290458,73363055,151909968,1000000000,184632890,166075631,191260392,295429370,117106320,42310885,667849064,191091523,386469103,217886242,971433186,18937753,254776010,7454957,935428024,99193386,797123274,926995047,200642784,37313912,89783920,99866019,12804029,1000000000,102154263,99522867,8304757,264414275,61892682,559690518,27477934,459137979,49526278,188112712,1000000000,1000000000,1000000000,120328104,136237122,338330920,84513114,1000000000,369497479,118623047,26698030,46424377,16626656,227835038,112286896,311690581,57216360,74169215,262415348,946911276,23249100,6318137,255916717,130359665,401586860,378227651,1000000000,1000000000,571874012,898792335,38356876,180100533,81080787,16092988,14732943,7540958,94029577,120276665,20662311,312953690,242444286,157127283,339209660,13389026,57005927,123157619,100173125,63309950,121937355,61720764,160490869,17696197,64421228,41294798,217426508,303947024,586211131,210110267,1000000000,45750564,119431824,106029209,300108753,22311048,4955697,14374127,187623844,173181761,324294341,246974225,141748323,24272745,12794769,722033788,183588991,271051064,445709407,106661734,51394670,48707996,107949817,25895776,437823655,155373989,81558485,148340265,843936360,16840481,295764831,1000000000,160857396,245268494,22095920,34532404,1000000000,115256873,101026650,56868960,96785621,48136863,283541126,753849818,61825933,150745687,8918977,13739094,6129669,83705414,253269724,9037850,630119290,86129420,401058992,155111163,89256685,195032817,86154615,76614423,228920890,50767421,5527389,292329929,194560983,23102501,804794629,188474475,163889853,260526489,101037366,291638510,160364110,143744,69123396,42899780,63399723,247897332,130894746,192605787,25001429,167996194,100439378,1000000000,69408313,77987540,30139988,145765578,1000000000,497450152,138051768,58214271,1000000000,130445084,151846828,77014346,1000000000,144641099,1000000000,13847414,1000000000,221887312,172533152,82209233,530661094,1000000000,1000000000,458195742,35903752,6542206,248161008,8807547,48638960,135481786,139757869,231155160,254757921,801347074,162708689,285010014,334149990,167661712,1000000000,256731130,212038671,699209422,53686156,986208902,80666477,1000000000,636512906,6119560,315241553,436131840,25866168,153821622,413634772,336524629,27223990,163251109,776700769,538605465,24033213,66529223,48884070,36094087,105068427,506177198,175136698,189912827,157068661,2268132,1000000000,474687314,1000000000,17132849,306989235,194346220,536806369,289489982,121866893,398310327,137905679,67508654,15053308,132532364,1000000000,455068412,3625673,87391628,1000000000,54528254,344365447,122535737,7165839,1000000000,175452678,227951593,32447557,879637013,187961062,272227177,82968526,53384238,96679673,126972003,106277239,322815617,32712290,166060255,185366270,111735569,180797467,179593327,95533045,112056215,1000000000,11493226,120961398,14094701,19618503,1000000000,1000000000,309162486,263696476,271609447,9094813,83957962,426565065,578989633,541425793,7822225,747307183,206910451,21251862,305792967,403234252,69884565,77105826,1000000000,14213880,632673450,337116403,117793269,470212616,1081943,126665538,372127489,83405420,5013808,2990074,193933772,404394140,139824616,353390,103523881,1000000000,4264235,49863668,92233948,542196698,244970463,534729280,6334905,303389259,127201320,59973118,220916766,28371955,158715376,224255352,1000000000,29091686,136347881,501359869,95250748,3227360,38375622,164959189,222284106,1000000000,585559617,530076823,814257809,479586861,72079001,200500863,45004259,72830,83343155,842681367,68640171,75464109,123300466,529617793,107932750,479155806,668985553,29104282,274036078,147065559,392657669,23413,70130979,212107308,595661156,143987994,385208058,606368716,1070424,130367147,9390742,416218865,935236145,376355399,196536483,238233514,1000000000,57609196,365202939,2595172,1000000000,451212974,46591971,205659826,1000000000,35622650,154822228,7326424,480529,132056288,5961659,1000000000,59880402,1000000000,15529037,18291711,56166317,44185311,175146706,213269426,130564614,20272674,174989706,139190527,183315780,25681355,1000000000,385933997,32492870,170996750,10939659,1000000000,130843482,1000000000,323606460,277805972,163041027,40191880,268459313,1000000000,1000000000,299353703,174465125,1000000000,316883745,46776098,1000000000,153224949,96198651,876247584,242707323,389457602,434435164,1000000000,161558709,274893684,397268692,53071926,13940589,1000000000,6542074,473222991,9254996,746967427,55262984,217696661,71801884,147420394,849802850,62259921,1000000000,87459159,206393063,1000000000,459874747,480075692,587102690,1000000000,1000000000,81020930,111269325,34829110,269355960,173413153,542510560,591429163,11027735,34787937,193344007,8553696,415838837,1000000000,95259672,487223654,296528132,133761509,266895520,165506352,128658611,5229264,1000000000,375276748,49474848,18333463,207879654,17043735,5279778,328751324,162124598,78201072,172167778,84430203,313772830,4510876,319929327,1000000000,496450804,199631259,155160941,156711538,53311616,1000000000,29536282,14058712,380219068,16301628,366999004,334155413,137516518,1000000000,287457210,87557834,61500718,13168141,88343853,28622928,334484031,186556792,131948404,67802880,799255,448998129,212663281,11876524,191679942,189068279,140062929,95053899,143645729,176929155,1000000000,10449293,451305310,375737993,21239705,517804154,116571597,252106346,76845098,76852011,658009526,245074720,155141532,81301749,71742082,80791191,1000000000,17155494,9465942,289133329,1000000000,112234605,284020793,428447019,61510139,303452174,179955221,153529912,282295200,112511247,1573946,369355585,476656851,436382820,26994292,239022630,272786149,225545522,122603873,33088722,1000000000,8556194,189187305,20871569,112724219,25866460,108187784,349816060,104176,49101114,94139637,45989982,80465941,432437355,281141120,168094412,54380783,17404876,885393094,4631270,219570299,172590186,112717938,107435299,275667885,480416603,33999193,227695991,214583499,1000000000,8336410,552719869,127365618,198393549,1000000000,369396027,13302429,751172551,23987058,456244871,1000000000,104030567,11510727,285791751,469628465,50386237,437550950,151647017,92791260,42317987,540145126,302836655,1000000000,469772033,40069485,314920739,50105222,121053417,590358953,229984951,37246452,156547186,40997433,86227066,96058053,1000000000,43788463,681756873,188646476,44390485,352112531,67629585,239469654,388951398,1000000000,274746053,640284367,100328771,577946388,116385853,10473721,131466894,59200159,177522333,232067439,1061313,57997487,118638664,157612512,109273326,104999557,1000000000,377345438,4990970,1000000000,134495801,979481487,265411361,815306180,41146769,1960008,313150821,458351329,66487717,100448579,225019287,1000000000,30383265,245767732,377320177,465646353,174552572,37506851,894526713,1000000000,65812533,358755400,1000000000,44760677,71715272,510640867,1000000000,206492010,738755246,1000000000,135486986,174149926,713864813,1000000000,36732250,29975516,21199468,218185467,14461429,521068546,30252514,96716001,1000000000,96412495,13451698,6147928,23328556,324925272,46759408,191985265,38475183,191861199,140988874,273038562,52906785,60975054,269159930,188652831,773233296,1000000000,132413214,259949938,1016136,52927371,73313906,330213213,211499538,1000000000,74192522,1000000000,173696037,169091623,6487721,555789933,989356660,268115227,52270985,43699165,46972798,371544924,167997991,49680615,713299266,11754607,519380037,46202974,12640880,158590275,235407551,1000000000,407317727,213120607,386582814,433316081,1000000000,93905696,1000000000,254906157,86033716,35109622,11476655,1000000000,108655587,911367783,7067503,31821349,712961762,145519538,291770626,327761529,77716090,52875270,22795234,177327654,79976326,86132581,7719494,445580603,145518203,224444544,355480956,79954423,76995494,237681809,73966312,851552295,341923570,66119553,385915229,247255913,1000000000,1000000000,21927654,1000000000,187074043,973175815,60358327,140593472,39075167,74211736,62245606,1000000000,87480441,197460697,78987580,483197144,444956198,249860224,1000000000,13746424,1000000000,55699803,145560911,75378108,218651202,25745733,61439109,227298311,277368598,28881863,142972171,58751509,1000000000,127738909,204417908,629927017,224979061,31761596,562257597,19189485,1119052,138954774,138935446,17677682,306662023,1000000000,69410624,1000000000,94350575,831387054,43645049,440893382,2855425,540596666,314647417,13645227,181480379,215685638,159146655,163968784,1000000000,157279180,207167050,58063885,151083150,1000000000,681207527,395439315,400463899,106152703,127152650,129229133,27600122,1000000000,416947418,1000000000,165167513,1000000000,400183308,20822993,1000000000,100378630,1000000000,5612289,166805870,1000000000,430764797,264858680,593581442,270699945,149012707,222161167,195553475,53017704,1000000000,622302371,190694337,316906865,149669780,8647669,3047713,408504864,337100525,361822458,33565301,305275145,88758782,409228128,1000000000,179242637,19556608,210025008,36251838,5991881,1000000000,277770956,665962413,57663002,1000000000,412927746,187428579,69808350,177035243,98575348,315691339,33637074,121365770,1000000000,28576187,340317252,177086103,152146535,709206079,1000000000,356041032,207784652,10025914,830800321,329907375,1000000000,5911354,30566184,97470557,25028311,25085003,33299395,562410192,672219124,50201030,8957990,163898666,281227325,420909643,286321197,1000000000,191079649,84323039,433374457,521487552,22154440,909120315,345257942,64261231,56844430,509447129,715972180,257815712,1000000000,98251208,1000000000,386243105,1000000000,124349192,398426446,26406415,1000000000,56383378,126048045,108289899,73948721,180846887,200550912,1000000000,1000000000,286177577,301295919,537008077,144661643,56458692,23622748,11630541,770184749,1000000000,116716348,7606066,354108408,35675844,30281971,1000000000,298751101,1000000000,305834366,1000000000,63730468,224050875,1000000000,177241110,291341565,137965189,170490912,475612378,986329918,36199308,1523437,1000000000,692510708,162518154,144116436,28598015,674552333,169361648,289438146,267251593,186057267,75142702,199679790,886750254,40683619,165621100,417005320,19897403,82207958,81218705,42038199,573749642,828864954,77027075,110378092,68237625,1000000000,87970803,300058305,41021210,94611629,713946201,118750083,45282023,135861933,21490030,290173676,56140355,106605163,463027158,664568733,98721520,18989951,413835201,95464548,368431301,384591345,58736915,701876877,174943472,284353315,77917670,399034582,70291875,29487691,1000000000,827710411,87319886,811336250,405185155,208460681,131081709,1000000000,253362196,1000000000,338374811,1000000000,178397278,566492,4301947,362892747,229464648,8913692,325534687,328434549,107102076,157893249,868816625,299996411,91006779,12099533,1000000000,491076141,63378132,458374793,6674548,134411185,71281583,176453417,171794855,1000000000,170436471,1000000000,97662594,427954413,784478508,468337,12060066,57234836,1000000000,375382397,330849980,67916652,39297571,66156593,1000000000,237084280,628333822,112941792,186630530,94121120,64902647,312889514,108963664,192110770,55770235,1000000000,29344432,76849055,40063182,225044736,587880376,170686807,21226030,1000000000,86608325,385437491,103763355,167477441,1000000000,403972751,218869485,29946257,114016871,279232317,755692345,1218155,155578769,338418,54852294,701653358,947303793,82439784,53145424,212890408,146816183,37473787,1000000000,341946990,1000000000,1000000000,71059099,493889030,407902882,74756115,103220200,75968223,1000000000,212500807,9119031,43354016,59044094,176442657,277474312,9373012,342756380,135172513,37637764,123559499,145632118,512504907,771616500,35507505,1000000000,49919787,1462474,411693078,944759593,132818971,1000000000,283276363,734354941,96456765,14015761,605082,81836012,112559689,162534951,109481548,23325379,1000000000,299710285,1000000000,342708153,250805776,207172511,27537758,302754318,12970155,320766020,350784885,849449138,669035642,9871755,9240311,85171615,143996821,808426882,607592746,64835141,56867003,47723453,1000000000,51999359,4216419,390004508,998069648,1000000000,41311509,318688193,1000000000,605142444,1000000000,101621575,219814750,39973215,407323100,90122797,75808422,114824555,241438266,53296058,12471421,60278883,260696367,19876365,25232899,244833701,7284421,749011526,179081571,13480630,26201837,520222180,43949778,10150589,444530176,865763666,12475086,27853585,557798713,985065430,46199221,8215919,416330011,95407137,454515523,147234393,7536860,96514444,29513797,320460837,83542719,136830680,39555057,126392488,10615757,154947255,1000000000,1000000000,1000000000,1000000000,398187606,36643545,1000000000,304034544,1000000000,1000000000,685596773,232754242,76713482,115542654,1249260,468660664,786993282,340884382,244859043,15302407,154163169,1000000000,1000000000,968281090,377435460,70633862,1000000000,1000000000,1000000000,236933659,385205298,75979641,215107963,194258663,819600842,1000000000,51738392,488854182,187265014,90992639,91346475,365324939,18940001,814332063,82714177,242485443,104188211,5130364,236454838,121308142,478127952,160967020,1000000000,18828135,239427181,137858789,432871273,153840623,100033863,631546234,193427703,89337495,227811420,266431750,152805014,1000000000,82972766,10284169,597504302,184697993,135796420,1000000000,191287576,169247392,580742281,1000000000,491727293,224579052,371496615,204863343,192095173,263655240,248021294,2575799,6835589,326572486,14426584,1000000000,305436049,28946414,79044341,44870013,118356227,45433097,386269232,120093934,267829139,107900882,151165395,123006911,101758304,279582449,209795577,1000000000,710406489,70569794,237223,174214583,55681915,344779792,16873475,4985784,446968380,402723316,105793663,213565752,72188876,30346458,450206381,201952620,83165067,151295188,117794,106800732,37573241,26521137,14046270,79687889,204972014,425155012,143528163,216213609,92690845,171746379,41188660,701630587,461087784,156478114,76858583,532791911,166099543,1000000000,329348289,216000513,623911346,559195803,500148288,19552141,358142637,476753058,94803325,1355974,419575713,3168469,14181575,824090084,16660837,203143018,31288389,2511166,69386083,275615855,42301457,693851256,659385300,193697565,136435418,155257630,101460544,115773232,361220463,97657858,1000000000,23195128,279387344,205772439,1000000000,117335965,93980997,79694604,19805897,121692082,967278423,123067418,120661350,15221925,1000000000,459635944,506725996,1000000000,82814329,637256180,370069418,40279023,339513118,4112153,16325512,1676291,878055948,28991427,314508631,107804533,188124650,218354239,100004896,1000000000,24278581,102305515,20299935,352275404,543170794,393920973,30267883,1000000000,68387564,909280685,1159300,1000000000,817758050,254564946,107097813,13945160,257512731,202900590,725205089,211747210,22702321,632363838,268133632,104153303,156139413,1000000000,239849864,62740854,166813487,320446405,9219111,269814038,65512218,2549974,6191942,10044363,42282927,195699864,428746356,146992978,541220315,83878796,1000000000,296092004,38068797,413380127,87750512,17603685,329618955,61678230,64422170,30757775,170688444,20373459,910858391,75427588,296235011,122290271,321393036,186805221,8207090,1000000000,289807497,183482833,22118055,169355165,78749261,238737254,22193862,17832836,105816464,247272564,127856364,492102308,71727341,1000000000,284167175,373615667,643407578,44455415,275891452,1000000000,37668469,116071050,154944320,324598441,36967079,5897595,69916470,378381780,145199843,250197917,512033372,21111876,425393146,4488449,161383416,20923708,51385539,551949265,298909738,151332922,117362176,186089017,63272045,266307045,15341854,11314596,419996878,102865113,2941638,1000000000,381206180,290400311,118466503,99816204,7511773,185924478,323601970,79626786,21459181,174620003,74948425,1738613,55108529,1000000000,250996817,75251499,37797544,13886003,151500245,1000000000,166950214,11436485,55429609,47239642,49437961,5242747,263411358,67800268,17286679,1000000000,922638172,338573121,44630385,104806085,171531268,1000000000,70636155,412676304,63878393,605207551,1000000000,335182507,84569876,563390104,373767000,282318000,9235622,13659387,138809202,456082175,464418206,308113014,45944563,210684240,76600070,628883050,199626715,119505895,380658709,242665868,39693521,501854464,124843540,14951869,1000000000,92110214,395326042,119757763,160848549,47438008,18951920,237485381,96990262,1000000000,431756777,57520572,24667665,19347565,443089145,1000000000,116035274,307323017,179291649,158749972,245721383,293374588,6039981,229378982,200742949,411865714,404703153,1000000000,67674246,51782181,217666818,3211924,483950081,380314540,501740752,10714281,24084650,410598846,12004967,16833345,112959382,1000000000,160353785,7391042,47417634,232768127,156216962,13172509,27899527,32264937,321992857,6124607,64585887,17776035,27042352,183652721,184261011,218563302,493056310,44413670,139855090,49625209,3965658,272277172,495966489,1000000000,188959484,161608174,157333307,119704591,304134,1000000000,15376018,271885551,96023332,329520,1000000000,84607631,291884722,20311685,148041927,1000000000,597764785,12941023,1000000000,141991107,20831925,121530827,551375545,1000000000,168801098,91428435,190891893,1000000000,728563027,3626417,299986590,19082975,343504170,163449407,795903147,394214574,9676287,101064734,31663259,243197230,42123855,170220855,272733477,525345455,235166010,45973882,452482863,457014943,37138978,42309178,92390585,862324857,290051340,70617648,248955598,10801059,58811189,109095781,4196444,26556614,1000000000,7791686,612743245,264284267,288155036,8609873,14010348,518010732,185991070,60920444,61386761,392573173,6133001,230943758,501825081,87796630,4803547,85349154,1000000000,396465215,13585575,920375434,93063195,40413588,18711186,64364857,122147378,549876372,150262624,191965550,38153587,1000000000,19863570,234156445,1000000000,3750997,286492315,22173675,1000000000,148164959,46115965,57657704,11726132,20053282,91032912,141364521,8933055,20934043,487783,340169819,873106923,298499122,61883076,91474328,92539143,14390754,1779527,248443912,1000000000,57742152,73210116,292676678,156234957,258045714,151039854,34275979,70860337,321907063,45410755,121460330,156461020,207067270,11706197,17644822,30342480,1000000000,37287228,9478774,1000000000,239564570,500525458,325476150,226911840,705399100,390153087,69067600,26251226,29299458,750720652,26459619,409692547,296760506,106388138,41486833,210121361,91376061,455884196,63905495,1000000000,136396151,304309009,110207970,1000000000,1000000000,52251456,269107339,732963334,1000000000,126365050,5513580,24377631,47759765,192834934,189433355,26220303,50841330,784058388,102829943,207223909,42736683,486991515,120265031,1000000000,156270,1000000000,236492115,1420964,699013,417891303,24733491,272691939,1000000000,3670309,10144564,12112912,202955385,653320483,91170539,228457210,2051538,294940637,105206564,81382339,417296697,1000000000,54386581,1000000000,33843992,360693782,71723695,79311552,234270731,208328423,186160223,38382007,79851645,2709132,329823703,148351162,100581450,681131387,3889967,593297914,1000000000,8694959,45686357,1000000000,134790503,290808341,169468941,503515625,344392973,60990962,67710418,231991620,1000000000,15099875,88140932,56988664,865020173,232253832,34033672,809553938,171247402,595276509,645868460,410166442,7106649,116505169,30524485,1000000000,7570476,315189735,149314332,4005759,242262487,1571815,864218048,111551039,157909187,14512335,7428146,157405029,99780511,646914,53056892,1000000000,0,162297907,621615030,86985661,14885484,222954134,787566739,129654332,89796673,7481025,484226114,211447102,136167626,1000000000,10355655,38992287,218337262,187377792,1000000000,279379533,151081862,22514650,565759975,147501959,159167672,1000000000,365920176,139540487,64133329,412000924,185258269,111783949,129412463,104346547,1000000000,1000000000,166405482,176081340,391907336,637827208,289100811,408587394,221053479,131608895,72921549,461210278,58365575,268525294,59191032,313478758,1000000000,38301955,19085698,16605890,328136003,147163722,1000000000,112240355,362646,364709686,34902170,431935471,216309045,102775190,191822793,436194804,100011454,43153611,418324054,40447613,127891926,1000000000,21909875,367077188,18204558,266604089,292910931,59119105,275741518,249888507,854423989,187241285,144278195,375629630,477871378,287528868,46337322,76912332,232256417,1000000000,704165123,21678216,1000000000,21560971,125524382,90673712,142570669,249101596,335230181,83200380,51088084,113014900,59930082,328677149,78773305,645188409,998301873,256558241,163457255,497984616,441736754,1000000000,72664190,407373850,22551368,96623991,38525977,103944839,163538229,262650164,7609549,125333878,205416400,64582280,515212327,15284816,5075433,15203979,950239,173506122,257217328,133252517,65017378,369367764,69874474,73745983,12188131,28514619,191015398,22499338,145079094,79390,1000000000,55234554,13996908,198759234,33268388,6715799,1000000000,296964466,626370766,74375749,74662018,43124535,91267575,51344595,1000000000,72469200,840949005,32539439,29390612,1000000000,38158607,2906367,7346331,67788923,343105107,17005978,27653839,268846465,5686606,1000000000,114655503,28351194,126032122,99793315,984330192,101059156,165449626,148096675,21208492,21086780,1000000000,30856810,2990517,33840828,395738569,215718571,1000000000,103744248,24617322,54036311,266193327,75633184,185124443,16025192,459681685,1000000000,287253463,320047308,434908461,145723258,404756697,11231696,15885932,30351392,306063513,1000000000,146541538,919930948,401400,376624995,76479101,406210857,154734140,30748974,310667099,193653370,103302911,134096047,90005293,440892356,74870481,325620400,22906097,287713911,114629188,42257150,324380361,8413647,1888165,872347925,430860416,59088681,4362435,1000000000,154659552,133677254,19147722,505855872,1000000000,302203453,1000000000,128971100,158197269,66110758,155546967,147794471,148030255,1516013,206719876,260682709,439770171,194052225,532145332,899564943,70770285,430909487,231827576,136718746,257473246,1000000000,239011862,116486442,432163,1000000000,367334341,224491048,683174318,4089982,707696265,41803685,314089838,351457948,2820944,75792283,222975194,60686905,291809537,645493447,1000000000,812477944,244692,426360295,50821373,855779063,55123185,135561303,315381111,335110492,87908418,49169174,591386322,489215613,357439352,286331564,125152585,236066863,144757385,348219970,266802334,246861820,61422893,107520697,123731734,285073483,123775921,66499289,246610003,25657082,20779011,114287512,94390855,568683473,137431802,664444937,2443690,341296742,249059020,31561577,554156165,15414414,251166515,79512017,19062970,82363614,1000000000,136553703,280788874,983701507,111429153,70263676,81888852,189949733,107897422,1000000000,337549812,539495648,96717117,220731765,103881558,134125549,13120425,39996377,46781293,3136846,287991458,166422166,38827,51401374,52641584,1903716,136200908,1000000000,122368079,83764705,1000000000,108158783,8657840,8105747,1000000000,30163818,1000000000,62532490,113966452,172444581,103400235,555651662,494105300,279557490,127012349,314810218,458331134,757530573,1000000000,40903150,106410325,1000000000,46446703,10256137,1000000000,19718808,1095975,596642904,1000000000,21377460,48003370,5460211,198802898,196787205,34943836,1000000000,73497851,151914441,292960434,54372075,227514850,45181684,7360099,211499409,1000000000,210581451,31012996,1000000000,359107510,731794760,184129411,339442858,921495934,248342720,2225689,8761918,6498310,553832445,269428440,2042718,12032905,145645403,1000000000,618768899,117001370,200668495,295573607,1000000000,37499919,323173972,478980763,527152720,96312294,1000000000,444215,322773606,172098286,142663588,80246339,91515051,23746999,111841642,292479579,60094811,494533110,61711694,1000000000,716915230,366811261,19232566,25552412,1000000000,152053959,1000000000,421341745,1000000000,279172040,46402407,239514408,1000000000,216546010,807270216,1000000000,247078393,82969568,753473368,1000000000,470442953,1000000000,285817222,1000000000,272433556,7272518,207272413,67347832,81028542,43954701,0,1000000000,228754164,154701206,124155672,25290565,316063696,293585174,256413655,446278712,611729686,72448081,1000000000,719378793,573630365,22240466,662370590,121236174,700676281,162428526,117721749,354108492,45288517,492372597,1000000000,263868328,204204524,1000000000,1000000000,13846577,509970909,288289166,1000000000,145923165,246815212,35196574,598692200,276349175,1375593,369538016,149585145,115854374,58506920,524129583,703251352,304198065,65911027,364523657,5312434,3482341,141841036,19744679,928880372,75890409,151906583,15808466,113177380,301088551,1000000000,39813760,98955353,4436391,96239303,13737425,512968057,404308876,980938017,144031651,1000000000,27651013,607847672,73331321,117403413,209335798,228434655,614804661,203181524,8331571,565866309,57503339,21063630,1000000000,19983277,4029340,96789171,34621339,12751598,46702664,13070782,36094724,409788657,32150986,1000000000,427129090,439826031,68985704,329350310,689629036,52339442,254454432,984264325,469685563,401770656,10895833,8322508,1000000000,6656874,58492019,42803008,524221105,603253739,545528841,12466133,567548656,55343523,165035309,250919762,1577593,193941476,103378086,420241774,1000000000,359098538,149052849,1000000000,239240378,263068028,284384868,115418749,2999774,88512950,217773152,1000000000,95927357,79691912,1000000000,139009434,23651915,34650053,90971152,90520044,2383787,1000000000,84612206,109384691,160273514,479771444,495063848,1000000000,15566780,130299360,5743631,43827105,520048389,89892383,12175069,1000000000,313737,45730179,170167554,1000000000,25215526,1000000000,201073,369430914,1000000000,178785421,60425466,204286823,1000000000,86300115,97870450,517592381,606523715,543850493,220218433,1000000000,262961869,38534131,260791493,40789109,764345419,16617098,1000000000,172241235,304740316,1000000000,421474696,260357046,200043506,1000000000,463999247,23878051,60187265,163211432,773884657,41307931,3214663,157830507,178260807,280903173,1000000000,73085531,124212940,608245222,1000000000,24669808,46160928,199394840,196022538,68930334,314542,828009295,206489553,1000000000,620602632,97068304,58752338,348030804,214146728,95008116,51128907,186004024,70611563,279836,240596929,1000000000,155349226,144168870,34569906,428646955,262209358,88321809,231856397,111608714,530408608,32517105,135705,305834239,8282587,914959333,669083003,114309682,1638638,1000000000,5618573,1000000000,61849488,1000000000,1000000000,298213292,321125140,182115569,79351230,13615035,41125444,108887752,138134098,444020983,9296727,30413186,1000000000,56643685,29556680,103275391,223051602,350575775,227298889,83198436,255252743,250754032,458218428,263467723,296856459,620892266,77858570,738906471,54596733,2014033,40836705,21284300,2397181,445195741,122398823,42549553,5864875,46763244,29931961,200133268,98473700,19733604,530060188,1000000000,44623498,358598883,1000000000,157409471,1000000000,380474858,19598326,259975278,1000000000,374768590,95695989,62848533,596232818,134100277,1000000000,148131234,235887088,162330273,181433506,293330668,408720676,281175665,171479526,35310060,155312427,78220687,389258731,798781991,169941351,1000000000,1000000000,71977465,40145374,17297971,214354729,190439570,1000000000,452664875,242310355,1000000000,139374150,34364837,39456061,587827557,136686915,365469871,5862703,666296082,57444175,1000000000,199792794,268119684,944930191,223304492,1000000000,52885120,97906435,1000000000,1000000000,777769287,1000000000,479543314,13926879,167347534,96742504,59784324,580788154,295968949,248304660,60645216,435769091,16041954,4579704,769538976,106934884,9878883,58682801,537724280,486052420,765321154,149352433,2088535,22489524,11864888,246727484,1000000000,94232512,11112733,17641126,453791634,81027980,656615325,1000000000,443210328,102881602,1000000000,102360690,5608367,142143169,683549517,46819784,120740456,1000000000,277410573,355083100,186900265,1000000000,521472100,562452784,8775479,221365922,226098378,700274624,17342561,1000000000,131902214,42739839,190332567,123964180,3572175,1000000000,113611981,114354496,43997921,300847144,22863662,43830264,313318519,171094357,162951728,795273726,289938055,582154038,53567942,261001656,535927949,63335555,76766877,223485267,215538795,5744886,994022144,65526625,372398328,253541987,21171771,144250399,85553646,125892059,2357874,1000000000,77743060,118061418,528162858,199615861,408949230,361479794,68935776,1000000000,1000000000,363314862,1000000000,8342936,112492177,912931192,269613654,97930389,226335313,406986107,39467070,314503266,92389265,2499850,98605386,1000000000,1000000000,112076793,72019474,39460055,292835805,605589308,5596438,1000000000,140031473,34302144,88106623,58158653,391101014,244357510,154987309,1000000000,88331608,79928484,222065713,574860222,95001664,17363705,563167677,33804590,40799641,395400593,408250041,1000000000,117598582,589688814,16325498,45560425,32922311,1000000000,67644868,429910382,468114582,105212783,164149372,75087748,215149710,205284923,9907327,401517875,555558226,111108420,63849995,552674119,1524540,1000000000,305174015,182023699,281567963,1000000000,189567875,202041437,521780214,314067820,54896348,81598239,47775187,327079506,639500679,41663583,2078707,253869682,123794738,156514771,57304462,937361090,49062053,32978768,54348529,1000000000,1000000000,189265725,551526214,127816036,1000000000,170544864,201642599,357697841,316468902,392119045,20649139,95599216,426580325,36134967,215935473,1000000000,813690371,795996267,101743342,1000000000,1000000000,373954572,91651625,1643422,172708243,982965945,538831108,854127985,346222342,197416870,100692053,19170865,830790669,35597888,1000000000,595172407,444144152,37519803,205610536,24130137,447057771,179033045,983966347,155850264,192177355,1000000000,115968247,73657442,164197653,37132582,150006296,67334986,1144383,929900981,81374306,627947304,19670835,110527896,315573945,2173078,19553028,1000000000,13730875,174264579,1000000000,60468785,133626013,111404255,42547446,236178710,1000000000,76779970,115286579,172590642,804834104,458310125,68501744,79528245,495422143,143096390,52087770,7204546,82656973,182222807,195919398,540024574,123308260,8311368,3033162,145961495,5170848,1000000000,23863519,177729612,200540253,28485809,1000000000,446213381,166916117,288297369,748134923,266974006,14120773,13547778,476266069,44757012,7208878,187238542,468421181,25868485,304543887,2344854,76364713,485622339,233122359,240174702,170808352,123041191,701081455,13292522,867046912,579478099,358298107,710142344,133076674,479146524,193315237,423117265,66073702,78854145,499225289,408820713,71333620,497364086,100406652,66430362,1000000000,1000000000,1000000000,1000000000,462756315,184574748,265912273,434570247,197570929,440537332,1000000000,1000000000,235780394,159196317,284199236,221471630,397718681,789322483,129059831,190070865,233005684,1000000000,47676451,401130173,378275485,683038695,1000000000,168092697,102882825,2830150,7419886,142265736,70892495,672728614,231405713,83018756,427357612,181491071,56475085,72563104,334301692,27948722,1000000000,945460063,166498599,47259994,990257070,174028151,9700934,19140006,17482313,1000000000,88743655,81517251,119220996,130922224,159951249,66541577,404923174,188002079,27056817,6402666,1000000000,219763133,1000000000,39899583,717059197,603664254,70360679,615399459,1000000000,167494850,1000000000,476931645,706688300,139321553,261261779,365003398,188967180,56296634,1000000000,360928534,4155111,125163316,1000000000,30281116,271117627,1000000000,1000000000,375305552,415496827,13743900,230654209,185431106,1000000000,312316991,22377233,1000000000,488683753,52930485,37221415,97048192,210934673,85926408,899519297,116529205,175789275,245543031,269010583,131558663,648955332,36990761,115106568,1000000000,437013692,12382637,204757364,984779067,437528014,376850261,194405330,82006333,226835521,1000000000,65081507,12314533,1000000000,784342916,287004256,109529530,8284826,431231133,453892041,38081166,14021794,150758081,389848250,428902229,12906138,562541153,126049961,436316162,52905869,1000000000,73131479,458751982,425920982,1000000000,50477622,153561603,56097492,394504,370777496,100735779,267479195,65121940,17085641,44512268,5022565,63922464,1000000000,124209441,134165388,503631118,29332429,52064558,1000000000,375480798,214994806,248893849,115710061,33361107,6322036,476225524,25330077,163709096,62147255,142410947,500685412,1000000000,1612853,634655223,233188454,72752952,640955135,89066273,416219091,1000000000,769671951,438092671,292057932,13667580,15815216,45850207,10577620,161611701,441852105,3982307,261839586,26699615,1000000000,77140791,983062901,588135075,0,187088331,267681018,121384966,144361628,1000000000,290291721,303974629,23123016,870460876,851903512,1000000000,37630149,182845247,279842442,51351251,1000000000,58693882,13146221,4281339,231169718,240587432,119812393,1000000000,108607630,11346291,13406438,27861351,134298268,39254941,18328074,258427390,72456167,6291678,115040612,336923315,149817729,50621356,21500100,105529081,134856020,458393369,224209233,160384613,16492518,107595083,269458458,1000000000,113848678,464518570,16949940,599915214,306157137,723809447,464537369,43354081,141210049,40169223,85659486,316604573,123977585,52819300,286604590,16109068,1000000000,164871325,525118290,77301633,49655481,303982141,47206873,134878151,447163578,1000000000,41810986,305811353,429523899,490543945,23181545,275797340,1000000000,1000000000,6812774,142504944,341879490,21646573,1000000000,154993703,1893659,179523799,36304235,402812144,77555805,2261313,15779478,466493018,431979239,9608184,445330822,120714231,15797827,245207408,75131633,542030441,1000000000,91354098,92636566,1000000000,1000000000,5316829,545119922,52534025,415591286,862552,368063920,138424543,89830088,32672755,314621299,294338435,1000000000,1000000000,85704977,1000000000,69343883,272026586,944746205,255091894,774935868,42753041,93251894,243571594,252566928,380781821,75928538,84840710,174925836,19231114,68425352,1000000000,17811378,181073410,689835679,85408589,57286292,540885974,269887728,276321827,248868916,17456881,148078906,258584447,459572173,485605952,507827851,400237806,381591718,234100193,371029521,196729556,133009555,88491203,56301550,243428379,159951903,309968368,264971345,84502754,93509131,1000000000,354469243,1000000000,1000000000,426588103,1000000000,22158609,75248487,33420588,1000000000,179078987,475537674,484268693,76763323,606481142,531363834,519173065,166791122,74565553,18772252,1000000000,163246015,161770943,32802732,24133583,262094503,169290710,45180028,53281876,284611817,55492729,1000000000,777395992,25192108,1000000000,333353393,212736893,230666698,59580747,1000000000,15632434,930029458,1000000000,482368259,433708972,503630831,1000000000,208483834,16042185,211787738,258885815,152057279,3364171,317499963,436687858,302296328,42060828,115427537,115668733,261488844,4012144,71541120,332170757,323252926,608691,130314551,970295495,782990862,337530483,12166445,1000000000,108147492,27959779,248686258,207146734,130931667,4705631,364239922,191024295,94567302,18396731,693577821,55177833,89566416,86685758,151274600,91711038,69026585,19940998,422213574,123992670,518224838,231993079,132040885,196678737,218339312,353970359,51482268,182075758,204945208,65976769,9806593,434417153,329387274,299946219,310683897,363567523,128738583,649339462,139060568,107837345,185441865,237146748,292540131,291342766,77367324,407602946,106442644,1000000000,118059816,474032791,288492819,19140306,117907117,162106903,269857230,1000000000,410783765,304971932,845281,20864797,305239599,26052949,134901155,1000000000,226644434,657083302,33837772,11967275,228559323,1000000000,177742275,66388078,109578642,951601933,142255771,70570401,15725004,1921292,1000000000,100352287,107350546,96967189,33113149,50950896,229299259,314227077,154902640,4880932,24716236,58879549,3127939,895863015,224049751,5712010,230090327,194259686,122173385,28262769,61240710,970893334,173076591,146124943,1000000000,205744615,11106915,180291844,126406556,142001899,118931618,333918564,113865344,449970796,458341339,376363942,241997213,650587774,346403803,130465768,460966387,56634129,109550021,40089790,939694036,547126250,5439020,48551615,25119331,1000000000,1000000000,1000000000,456109828,89105738,314319954,1000000000,307235251,140400856,1000000000,1000000000,14935920,30700798,30450086,167290068,240800764,268832663,11166190,282920170,134331979,514236210,327502208,208775378,136079940,93549560,242629174,42688887,400988154,848366128,57523960,90600815,1000000000,1000000000,282164768,317493714,251100448,226232924,538993454,726688214,3709750,707688042,573165928,143002099,148353868,144581386,2481323,8025623,1000000000,54170806,437685901,182958026,42885606,317726537,1000000000,44339869,149453126,515857312,230911346,42958560,69094539,60447949,351070692,140189749,9767791,377192449,209827018,327455942,429748459,260262613,1000000000,110863690,309081773,95444881,189678239,14697633,101456193,35161170,1000000000,159833820,188557487,80301928,410602514,72004080,271535818,76318002,189823420,167501066,97826252,160807902,1000000000,163537940,322202042,279679012,293505505,946752828,236759168,5315835,98583150,124381000,283632077,1000000000,30126717,381728254,159301321,232796046,674771551,140902519,82081837,150211721,88976996,69097473,78302593,107510254,34989574,31397908,1000000000,7868304,920526750,59321224,84684380,1000000000,755985094,355268393,273492586,349595932,136102870,92803595,4917903,30777182,423924435,109575562,411713030,7157151,94790673,114606336,1000000000,192179403,1000000000,82223292,388109131,1000000000,1000000000,449009107,98427326,153222188,387400851,154428322,5757734,20342508,1136871,1000000000,655244366,362608425,1000000000,163462439,1000000000,425240607,45624211,105071235,26042522,517068411,339821447,34494345,210511486,92564420,148115516,159353328,63965078,211143820,544819598,445134,619970328,333237722,20548448,274796625,54141958,995852326,86572106,13910589,1000000000,29118522,187057339,109775184,265663046,651315622,14745278,535359678,1000000000,255491924,182101873,510338609,1000000000,1000000000,526535566,367215631,253742060,5844161,29388757,1298367,235930884,1236551,109556550,293269355,64047487,1000000000,10237148,416610101,1000000000,328888156,92664211,1842263,1000000000,1000000000,384298520,401670920,157588418,546672573,174678509,49842229,4343338,386327814,122676784,130879067,594429822,235439256,19875643,236355002,674178452,532368436,85432735,1000000000,18430541,1000000000,535660305,147475505,22309934,162351900,96399668,61949525,1000000000,606067430,375769932,64824139,202163009,185183936,592836534,825425633,1000000000,123830640,485827291,298433158,237415383,104503434,667002161,275388655,1000000000,17167673,274538346,63493670,302952580,101471069,158475955,374170229,5329800,83195003,1000000000,1000000000,41231462,522616346,136334072,431943078,788466179,86132450,213387701,25842955,18481618,547823230,154026445,261261696,28075900,16204727,674722217,564731246,84933180,34849818,123509507,67713075,488027998,80754083,43641340,128092086,709730579,123281369,983793007,34191612,267747853,169964878,537939819,84290668,353306951,13290740,63304162,1000000000,182621,96599194,22231450,534729155,280065276,96278095,258331845,118244060,184244080,142909,636583855,86965526,428407491,357761840,1000000000,374056224,497653052,203497978,135560065,153400254,267798988,1000000000,59820523,18376143,307932142,482495330,284443185,108158112,58101018,51309434,219722964,715108982,121157584,29024770,22170825,1000000000,109658108,627583797,28915304,33493954,56029099,85766141,322078298,466082795,16325466,28127502,341115077,215688221,108253783,218327217,124273579,267853108,1000000000,1000000000,231166219,143013232,46445700,297938710,164142257,56608341,197897845,161448198,42041134,508686,131421194,280225963,705541747,42452599,69792721,22510304,40862396,113820110,6885570,7703032,101780452,82296561,293512898,103496832,132434205,123335531,137613705,1000000000,153878788,79475924,71927578,392831997,363445288,1000000000,20504407,221555886,139500647,60088424,115946464,140177990,337830364,145992571,195989927,115934765,8239852,383669409,1000000000,447493149,1000000000,29044374,1000000000,40174235,540494944,481018654,981650084,274724978,46740410,170161720,85226670,146699134,8098844,20046125,79893747,807222950,53563704,10428606,134570542,1000000000,117625398,465692911,197479436,300169279,41255234,30150220,111754311,235604091,183062012,821416224,825937049,170858355,818782296,1000000000,456307747,28123076,82389278,560306601,120833571,222746338,126688703,422072633,646447002,449506871,146664044,7832418,910487460,170958401,463005459,338240306,43985703,105366534,1000000000,143618622,1000000000,5897355,57539132,384832531,9842872,290249127,369512323,183590655,50679598,1000000000,158205503,103310753,69613882,289289691,450710446,221955211,367349131,385310874,827599445,422273092,7983506,20688458,107815204,707946906,1000000000,286080956,364506655,556732319,90994220,65215804,1816675,873481744,884787078,119258777,197287714,504606686,62377299,18278561,170548173,449057391,127590051,27071415,23863913,410864589,282961215,47810767,516077442,263207727,68700467,105395283,27613482,42650358,33658609,187577080,47810313,122617670,340311024,265631676,5926505,350150448,104409020,9039131,565733941,120326681,186543796,1000000000,214077866,72098635,1000000000,498812393,292459753,1000000000,471830504,238203388,15723676,164030027,172189512,149769143,321690126,28167963,12624576,535988558,90492231,9486822,715034043,49042499,108926259,1000000000,27929177,827353670,378748666,26047968,123913434,11045952,158991557,82779253,124475518,21539295,1000000000,386270572,19072179,73183049,151995230,299860568,36164008,148936663,18188911,92397658,75497502,1000000000,514776671,1000000000,580243601,27174069,16541133,137317407,108249373,271803190,358443703,476575823,115191214,262575014,29579153,553250816,56417821,175377913,80935658,388865609,200570705,1000000000,264521954,374427374,51531461,265217271,2525682,82379418,201003934,40912532,454187663,98260287,164463846,72211747,24574934,52947754,27502669,359171200,19067288,591121190,258229232,1000000000,354778534,242017967,423713084,407417606,18753150,143926258,278774965,400396059,1000000000,1000000000,636128411,1817724,273236714,71781600,27798340,191047736,749094,388210093,1000000000,44823721,182991379,426857029,18423615,46038650,333163776,45771488,44642623,212612692,392707204,206708860,284861365,247339499,13202952,81580832,19827202,1000000000,39708543,614291270,267483063,4424490,38392420,191337797,104842082,1000000000,1000000000,1000000000,138741974,30518428,415615370,62088754,713205428,245942947,339822603,102218404,1000000000,1000000000,3871081,209998482,34249009,120481966,42906801,15061201,326465781,384708413,47660943,221826477,505516508,29000403,253424578,84290830,56070512,431279130,187587863,13963568,119600545,62529042,19638094,354827772,1000000000,316734866,3666721,1000000000,132469799,8679625,432338402,201954646,54065247,59545938,52378006,438806446,24681614,1000000000,159259629,404815809,117802341,280455078,3433615,149087359,1000000000,232316536,10638249,220691075,44006772,106289969,176025771,20128952,313097846,2537565,710606133,17802300,243676060,472088794,6879471,125499558,794128282,127076201,340145531,479925240,24540551,4314842,139182443,23394944,85309958,283760092,44582463,10121673,747652661,607846166,73692998,156611054,136636853,54470866,203878298,120075197,267291920,31930965,13568116,212259905,252257390,243268961,350848520,86946326,37301291,145805272,162728335,142849614,279270595,290654209,49787798,52374355,240995168,464105417,91314430,111601175,75488622,373436508,24577921,26839031,74680943,97464478,7812367,228551827,349302088,37695024,641130419,72988373,430932194,164187983,161204251,643538364,351718529,183639014,10923731,32499203,1000000000,374073813,24261893,155939028,738135005,1000000000,118468067,253233349,1000000000,416130853,420476479,1000000000,91761350,469956253,19898483,478181482,41197961,300382740,291755187,14283747,30727259,19252004,654567104,115278868,150983872,229695603,117919656,393105072,1000000000,31671509,17974243,98122866,265055739,210200087,10473789,389957236,1485648,12108538,88904654,622904655,75157119,1000000000,41785871,3502970,112618062,162661593,118144723,411135171,1127938,25297068,519341024,12498034,200929686,103063764,110707682,64062145,152856057,106518091,132493755,472860182,190891175,79107588,1000000000,336166973,133916111,15941720,303919374,77671056,367184930,280796658,448314816,306957737,1000000000,1000000000,297586508,810662093,1000000000,36237892,200038228,828757692,56508838,360134789,224525736,91782108,108862959,62482722,1000000000,516584745,16611487,5388706,8592853,74343600,413114071,103310210,221592498,10809742,1000000000,552721149,705535447,184727621,775786810,137284812,459181371,339310798,3604720,70354497,236637301,1000000000,136960425,127312765,54672453,177203801,227649,247429113,30008082,310867717,134070268,697065076,34154313,379604298,123469548,707201639,82812373,406443994,1000000000,315482983,162001008,158346760,157191726,1000000000,239018825,359511029,219814081,9881724,112353424,55494866,121706141,720973542,382380566,228511609,1000000000,69478038,34069209,33348015,101884026,58646028,27226510,11255148,1000000000,1000000000,1000000000,341866103,281835053,65222885,103594980,4295543,528504723,14684711,1000000000,471852579,572836726,1000000000,77008209,360948599,13994803,72785334,254190248,22271362,394899194,403015252,331854248,445184557,42911810,73689426,117753802,99709516,48037103,75311263,456203811,49373344,566422003,426817216,385588626,345610644,202602066,114359780,31117589,8986707,32295288,412061182,117501854,1000000000,16336301,409584120,568474077,49143487,403855765,121081950,8639351,293892347,1000000000,298685928,193683436,201141493,326915645,111468237,216883014,129304491,1000000000,247380427,101845677,85477498,193884365,20977891,3471885,988982200,489272215,45063723,355361617,289600249,47098323,221977169,947779256,276434154,79444276,185707462,9692328,916044780,284179033,155861881,71756563,309345602,33403073,242574027,307098172,119857585,686170736,21040963,331775720,495503070,419034527,18654685,1000000000,28256512,6253070,9662930,1000000000,196871687,411415788,1000000000,27391425,124813558,5149919,38468222,337048332,190790428,345714852,257368722,1000000000,141268458,40996623,1000000000,1000000000,212413756,38490837,1000000000,14704868,365871004,1000000000,324616662,389323658,1000000000,1000000000,1000000000,13307829,1789082,136022150,118646080,1000000000,51872695,183389514,15261717,268940100,373434150,65456835,383473032,41187757,411624365,338144150,16937874,451357274,609770567,216166045,154538657,716761012,151738835,9606848,1000000000,44731519,63411944,497169299,29315742,772429773,23690492,654430755,59310883,587778962,301181316,1000000000,413743618,478921913,148392264,162991536,1000000000,81380462,113532182,37208436,437601526,203068781,212424500,382033,6345969,1000000000,1000000000,542252229,481837996,416391823,442982276,45731097,348936288,1000000000,79759913,433984866,20045655,185388843,253441462,89540125,294997808,30361998,498345246,416350203,593872248,110741782,192386692,295995467,527543486,2120907,34668183,73807538,123858400,294186095,92293724,922996464,629918862,634441,43384539,47906984,690960654,78450622,133335962,126157985,673992806,132923186,12748379,863739634,45128403,789390800,146790181,44970510,91865124,2450110,872330,1000000000,573625905,188578157,14182204,718810470,371201059,47431647,202565635,99917253,1000000000,23078927,252164531,208550892,64795506,32961885,333991426,739762391,240286097,7999189,50119901,71007028,115844491,359271491,1000000000,1000000000,12066775,6027804,158613508,199224198,75762180,87480653,136373919,1000000000,128019288,119487922,1000000000,264372067,8326911,755135212,280976070,593909497,117980772,91376036,149177135,590076153,122416865,14626185,124369426,39938587,546992630,27720214,83697786,147877580,1000000000,1000000000,65245635,402722096,219980756,617618448,119886080,2609798,52324837,44523816,66845090,263396793,26357307,161109085,215272518,189207930,14385411,32708840,1000000000,48281642,148071897,23717307,3349917,132747905,347733057,303002711,70992857,72101963,245758373,935671320,182430,1000000000,109709785,6339667,952843407,92897350,111899178,143571291,1000000000,189209887,126934605,29750347,1000000000,774808014,127964840,93106580,202997186,22824059,431927212,118786766,1000000000,67610762,1000000000,216854950,1000000000,823282203,104522458,281907073,247849570,269129784,208359393,108519825,174337904,167328363,3597005,121679721,334812382,680317711,295764778,1000000000,586047331,20730558,1000000000,114594591,59909876,4818389,214787713,366208240,267961990,8143866,176640767,635683428,174373052,77636744,112564877,692650218,1000000000,82643323,255766912,438364960,7527764,476319917,132713544,118520595,265162154,51786467,608890356,283813321,407998655,359440262,818439442,65942868,25172936,41869291,511815116,395931413,622674973,159255351,1000000000,69953536,108729403,1000000000,72667783,332153142,128287280,104405632,268440668,89504968,34139287,179635543,627162253,219302719,1000000000,20823341,187910900,77036360,100959773,153975995,297356345,1000000000,239440987,400400193,221222270,4059102,186881484,308010131,144990186,303012841,363455977,1000000000,163983392,1000000000,4501186,675766434,1000000000,40867657,244807321,107935089,409445271,504432772,347586557,1000000000,36472636,302106756,75779776,1000000000,31898095,29902488,463935331,633870869];